New software release

I have just released a new version of the libagf machine-learning library.  This is probably the biggest revision since starting the software project some seven years ago.  The main addition is a generalization (called "multi-borders") of the "AGF borders" algorithm from binary to multi-class classifications.  Rather than pick a single method and implement that (such as one-against-one or one-against-the-rest), which would've been quite trivial, I rather chose to generalize the whole business.  For more details, please refer to the paper I submitted to Journal of Machine Learning Research.

I think this is one of the first times I've created software without having some specific application in mind.  I wrote it mainly for the challenge and because the library doesn't feel quite complete without it.  Not to say that it won't be useful for many prediction tasks.

Here are a few thoughts on the creation of the new software.

On preparation

In preparing the "multi-borders" software, one thing that struck me was just how quickly I got it up and running.  Perhaps this is just experience, but I think planning and preparation has a lot to do with it.  I had a very good idea what I wanted to achieve and while I don't usually write much down, I have everything planned out in my head.

There are two components to the software: one for training and one for classification.  At the training stage, all the software does is read the control file and output commands for the already-existing binary classification software and then output another control file for the classification stage.  I got the first stage working long before the second, largely because testing is so simple: most of the input can be made up on the spot (i.e. the arguments don't have to refer to real files) and you just check the output for correctness.  In both cases I spent maybe two to three weeks coding and got things up and running after three or four tries.

I object

I'm still not sure how I feel about the object-oriented programming paradigm.  Usually I think it's just over-rated and anything that can be done using classes and objects can be done at least as well and with more flexibility using all of the features that made C so distinct from other languages of the time: pointers (especially function pointers and void pointers), unions and structures.  The problem is because I'm still stuck in a very rigid mindset that says there's some kind of right way and wrong way of doing things that I haven't learned yet how to properly program in straight C.

Take the dreaded "goto"--everyone says it's bad, but it's less in simply using the goto as using it badly.  In the Elements of Programming Style, Kernighan and Plauger spend many pages showing how to clean up code with gotos.  Gotos definitely have their place, such as breaking out of a series of nested loops or cleaning up after different types errors without a lot of repeated code.  In a couple of programs I've written for the new software release (and elsewhere), I've demonstrated to my satisfaction how to write code that's just as hard to follow, using only structured programming constructs.  Void pointers provide an even better mechanism for shooting yourself in the foot, but also unprecedented power in an otherwise strongly typed, compiled language.

As I mentioned above, there were two components to the software.  The first part was written "the old-fashioned way" using standard, procedural programming.  The second part was written with objects and polymorphism.  Of the two, the latter was definitely the easier to get up and running.  Perhaps this is the main benefit of objects: it doesn't make the language any more powerful, just makes the programs easier to think about and debug.

It can also produce code that looks very elegant, at least when viewed from a certain angle.  The multi-class classifications are based on a hierarchical model: you divide the classes in two, divide them again and so on until there is only one class left.  The class structure of course follows this logic as well.  The elegant part comes in the fact that the same method is called all the way up the line with no break in the symmetry.  But in order to achieve this it includes a very brain-dead construct: a one-class classifier (that is, a "one-class-classifier-class"), a fairly large piece of code that doesn't do anything except return the class label of the top-level partition.

Finally, here's how we might be able to do better than the O-O framework using the features of C.  Here is the prototype for the re-factored subroutine for sampling the class borders from a set of training data in a binary classification problem:

template
nel_ta sample_class_borders(
            real (*rfunc) (real *, void *, real *),
                      //returns difference in conditional prob. plus derivs
            int (*sample) (void *, real *, real *), 
                      //returns a random sample from each class
            void *param,        //these are just along for the ride
            nel_ta n,           //number of times to sample
            dim_ta D,           //number of dimensions
            real tol,           //desired tolerance
            iter_ta maxit,      //maximum number of iterations
            real **border,      //returned border samples
            real **gradient,    //returned border gradients
            real rthresh=0);    //location of Bayesian border

Yes, I do like to freely combine different elements from different programming paradigms: it's what make programming in C++ so much fun!  I could've passed an object with two methods to this function, but chose instead to pass two function pointers and a void pointer.  The normal method of calculating conditional probabilities requires an array of vectors (coordinate data) plus an array of class labels.  You could encapsulate both in an object, but this seems a bit limiting: there are many other things you could potentially do with them: for instance you can pair the coordinate data with a different set of class labels, generated for example from a set of continuous ordinates.  By having them only temporarily assigned to the parameter list the program becomes more flexible.

This is one thing that always annoyed me about O-O programming: the idea that all the data has to be hidden and then you end up with a whole bunch of pointless methods that do nothing but assign to or return a field.  Sure in some languages (such as C++) you can scrap the data hiding, but then is it really object-oriented?  Instead you end up with the older C-style programming paradigm with structures, pointers and unions.

Finally, suggesting that the object being passed to this method is simply a binary classifier obscures the true generality of the method.  It is, in fact, a multi-dimensional root-finder.  rfunc could be any continuous, differentiable function that evaluates to both positive and negative values, not just a difference in conditional probabilities (i.e., a binary classifier).  It makes more sense (at least to me) to represent it as a function to which you pass a set of parameters, rather than as an object class.  Again, this to me is the beauty of the C++ language:  you can choose amongst a multitude of programming paradigms most appropriate to the problem at hand.

Meta-programming

Another major addition to the program was a hierarchical clustering algorithm.  I wrote this to help me understand the travelling salesman problem, as I've mentioned elsewhere.  The program builds a dendrogram and then, using single-letter commands, allows you to interactively browse through it, assigning classes along the way.  It didn't take me long to figure out that you can output commands as they're being input and then feed them into the program again.  And from there, it's not a very big leap to see how you could write a program, that, instead of using the C++ objects directly to manipulate the dendrogram, uses the one letter commands from the interactive utility.  This, although the language for the dendrogram browser is very simple, is nonetheless a type of meta-programming.

It's also a technique I've used very little in the past.  Perhaps in part because it's very easy to abuse.  I remember once being in charge of maintaining a large, motley and rather finicky piece of software.  In one part, the operations to be performed were first written to a file in a crude sort of language.  Then, the file was read in again and the operations were performed -- achieving absolutely nothing in the process.  I removed both pieces of code and rewrote them so that the operations were simply performed--with nothing in between!

Since learning lex/yacc and starting work on some of my own domain specific languages (or DSL, which itself is a very powerful concept) I'm starting to use this technique a bit more often.  The training part of the multi-borders program, for instance, does very little except parse a control file.  In the process, it prints out commands for training the binary classifiers that comprise the multi-class model.  I could've run these directly using a system call, however because parsing the control file takes so little time, I chose to compile them into a script instead.

The other day I came across a chest

in the woods, buried in snow.  I opened it up and sure enough there was some treasure inside: some coins from the Dominican Republic.  But I didn't take any.  I know, we've all read Treasure Island, we all dream of finding that massive windfall that will set us up for life.  But what if, when we stumble across a hidden chest, instead of taking what's inside, we add a little bit, because, after all, what's a chest without treasure?

Re-post

I notice two posts on this blog, "Women in science," and "All men are rapists," have been getting a lot of traffic.  Certainly they make nice "click-bait," but this blog was not meant to be political.  Of course it is the arrogance of scientists and philosophers to claim that they deal in "objective" or "eternal" or "universal" (or whichever other superlative you care to use) truths, rather than pieces of the moment.

As other posts make clear, I am interested in moral philosophy and the morality of equality is one of the most important developments in Western thought whose ramifications have yet to be fully worked out.  The idea, however, is taking considerable abuse from modern feminists.

In any case, here is an older post, that I think much more clearly reflects the "spirit" of this blog.

On the negation of modal verbs

I recently learned (it goes to show how diligently I've been practising my German) that Germans use the phrase "must not" in the opposite sense of English speakers to mean "need not." Thinking about this, I realized that there is an implicit "or" in any statement involving modal verbs and the sense of the negative depends upon which part of the logical proposition is negated.

For example, I would translate the phrase:

"You must do A"

into a logical proposition as follows:

^A -> P

where P is some form of punishment. Or:

A or P

We could negate the phrase either by negating the whole thing:

^A and ^P

Or we could negate only one part:

A or ^P = P -> A
(e.g., "You (must not) play in the street.")

^A or P = A -> P
(e.g. "You must (not play in the street.)")

The first example would seem to be how the Germans use the phrase since whether we do A or not, we will not get punished for it, while the third form is more in line with how we use the phrase, that is, A implies punishment. The second example seems rather more ambiguous and in fact inverts the construct: now, getting punished implies that we have done A.

It has rather deep implications, since all of ethics, law and morality is related to the use of modal verbs. Can we use this idea to justify breaking the Ten Commandments?

I translate,

"I shall go to the store,"

as:

F (uture) -> S (going to the store) = ^F or S

The sixth commandment becomes:

You shall (not kill.) = F -> ^ K = ^F or ^K = ^(F and K)

You (shall not) kill. = ^F -> K = F or K

or perhaps,

^(F -> K) = F and ^K

The second says that if there's a future, there may or may not be killing while the first and third say what we want them to say: if F is true, K must be false.

My dream

Recently I asked a friend where she and her family go to walk in the woods, not realizing that not everyone considers it as necessary as breathing (the jury is not out--it is).  During Bible study one night, we discussed the question, "How did you used to find meaning in life?"  "How do you find it now?" with the implication that before finding religion, it would be normal to find meaning in drugs, sex, partying, etc.  Though I said nothing (the meeting was in Germany and my German is rather weak), I thought to myself that I was always closest to myself, that I found the greatest joy and meaning in life while experiencing the outdoors, whether walking, cycling, skiing, snow-shoeing, and I still do to this day.

The green-spaces in my vicinity are drying up.  Luckily there is one small patch of wood nearby and the owner has even generously cut trails through it.  I keep meaning to go meet him and thank him as I suspect this tiny wood may have saved my life.

Now I don't mean to be ungrateful, but I also believe the configuration of this space, which is right beside my house, is somewhat inauspicious.  It's not an easy concept to explain, but lately I've become interested in Feng Shui, not as some mystical art, but as basic common sense.

For instance: where do you camp?  If you park your tent along a sometime game-trail in a corridor between the trees on a windy night, as my sister and I once did, you will not sleep well.  In Feng Shui, we think of "energy" or "chi" moving out from the camp-site along the trail, but I think a better word for it would be "spirit."  Energy already has a precise definition in physics.  Spirit, by its very nature is ethereal--difficult to measure and without physical form.  Surely the low level of stress of the wind threatening to blow away the tent and the possibility of feral animals wandering into the camp-site would serve to reduce our spirit?

Quite the opposite of a camp-site, parks ought to "breathe," the spirit flowing uninterrupted through trails and other connections, but with sheltered pockets where it can "pool."

Living in Washington D.C., there were at least two routes out of the city that weren't open to motor vehicles.  There was the W & OD trail, built on an old rail line, that ran West along the Orange Line through Falls Church out to Leesburg, ending up just past the first hump of the Blue Ridge mountains and just shy of the Appalachian Trail (AT)  Then there was the C & O canal towpath that ran along the Potomac, joining the AT for a short distance.

I used to take the commuter train or cycle along the W & OD to escape the tension of the city and hike along the AT.  These long distance trails were linked to a network of smaller trails: through Rock Creek park, along the rivers, yes, even through my own, ghettoized neighbourhood in Temple Hill near Anacostia.

I couldn't help but think of these trails as a lymphatic system in the body of the Capitol region.  Transporting the bad spirit from inner city crime, drug gangs (not to mention the dealings of the Whitehouse), and racial tensions out into the surrounding countryside, where it could be purified.

Back to the wood behind my house: it is bordered on three sides by houses.  On the fourth side you used to be able to ski to a golf course, but now the owner of the next property over (not the immediately adjacent one) has erected a fence which blocks you.

The last time I skied in Gatineau park I took lunch in one of the "chalets": wood-heated cedar cabins with picnic benches inside.  I'm certain that these were copied from the Scandinavian countries where skiing is a way-of-life.  I'm also certain that they lost something in the translation.  I imagined these being, not lunch stops for spandex-clad racers bombing along meticulously-groomed snow-highways that form useless circuits, but rather way-points for travellers skiing a single-track trail through the middle of the woods.  A trail that usefully connects two points, that actually goes from one place to another.

I'm trying to imagine a world where I can put on a pair of skis starting at my house and ski for the rest of the day without crossing or retreading the same stretch of trail.  Where I can sling a backpack and hike through the woods until I actually get somewhere, somewhere that I need to go, rather than back again to the noisy, inefficient motor-vehicle that transported me to the trail-head, ten times the distance I ended up hiking that day.

More on the Vernier clock

I've noticed on the statistics page that people are visiting the "Vernier clock" post.  All I have there is a simple animation of a clock with a Vernier scale but no explanation, so I thought I'd write a few more words about it.

Many years ago, before most of us were born in fact, watches with a second hand were expensive because they were difficult to produce.  Meanwhile, those of us who took physical science degrees before every device in sight became digital are very familiar with a type of scale called a Vernier scale.  With a Vernier scale, you really only need one hand on your clocks and watches, or at least, one dial, or, if you desire a second hand without any added machinery, you can turn the minute hand into a Vernier scale.  Or, perhaps you have second hand, but want it to read in hundredths of seconds.

The idea behind a Vernier scale, is that you make the measurement based not on which tick mark is being pointed at, but on which pair of tick marks--one on each side of the dial or sliding scale--line up.  In this way, it's not important how far apart the tick marks are, what's important is the difference in spacing between the first set of ticks and the second.

Lets go straight to the application to clocks, because it's actually simpler since the dials are cyclical.  Suppose we are dealing with a minute hand and we want it to read seconds as well.  On the outside, there are the usual number of sixty (60) stationary tick marks, one for each minute or second as the case may be.  Inside, there is a dial that turns around once every hour.  This dial has 59 tick marks.

Since the dial must move 1/(59*60)=1/3540 of an arc to go from lining up along one outside tick to lining up along an adjacent one, you'd think you're reading in 1/59 of a minute rather than seconds, which of course are 1/60 of a minute.  The seconds readout, however, is centred around the current reading for minutes, thus it moves forward every minute, producing an extra reading.  (Gaah!  this is wrong)

(Edit: I lied.  It's actually simpler for linear scales.  Take the number of divisions in the smaller units and either add or subtract 1 larger unit divided by the number of divisions to give you the spacing of your secondary scale.  E.g. if the units are millimetres and you want a reading in tenths of millimetres, your secondary scale (i.e. Vernier) will have a spacing of either 1.1 mm or 0.9 mm, depending upon which direction you want to take the reading.  It doesn't actually work for cyclical scales, that is you can't divide the dial up evenly and still have readings in minutes and seconds.  So my animation below is complete bollucks--the virtual dial is not circulating at a rate of one revolution per minute (this would be true regardless), and it's not reading in seconds either.)



It should also be noted that the ticks are lining up in a retrograde manner.  In the animation, the "virtual dial" is actually moving clockwise: thus there are actually 61 ticks on the moving dial--thus we aren't really reading in seconds, but in 1/61 of a minute.  I didn't really think that much about this aspect of it, however important.  I just made the animation as "proof-of-concept" and because it looks cool.

I find this concept of a "virtual dial" fascinating and think it might somehow be quite deep--sort of like a phase that travels faster than the group velocity in a wave because of how the different frequencies are interfering.  In other words, you can have electromagnetic waves that travel faster than the speed of light, although apparently you can't transmit any information with them.  I never seemed to be able to quite muster the mathematical chops to fully understand this stuff...

I thought about patenting the idea.  No dice: it was patented back in 1942 (U.S. patent US2293459)!  I also though about taking out a design patent on the overlapping slats idea, but even this is covered in the 1942 patent:

So is the idea actually workable?  Here's a guy who's actually built a couple of them: http://www.gizmology.net/watch.htm.

If a picture is worth 1000 words...

How about a picture with words on it?

If money were no object

I'm not sure how exactly I got on Quora.  One day I started receiving newsletters from them.  What is Quora?  It's basicly like Yahoo Answers, except for geeks.  Or at least there seem to be an awful lot of them frequenting the place.

In any case, recently the following question popped up in my feed:

"If you had unlimited wealth, what scientific experiments and programs would you fund?"

Since this is very much in the spirit of what we're trying to do here, I thought I would re-post the response to this blog.

1. Artificial life and the origins of life.  What conditions are necessary for the existence and creation of life?  What kind of life and life-like sub-systems can arise in different systems? What is the overarching definition of life and how does this relate to the laws of physics?

2. Practical super-efficient vehicles.  The internal combustion engine has improved in efficiency by leaps and bounds.  Sadly, this has not translated into more efficient vehicles.  Instead, modern cars are simply more powerful.  On the other hand, it is now possible to exceed 70 mph on land using human power alone.  Imagine what you could do with a five or ten horsepower engine, for instance that you might find in a model airplane.

3. The "empirical" metaphysics.  What can introspection and altered states of consciousness tell us about the ultimate nature of reality and the universe we live in? 

4. Cheaper and more efficient orbital and escape space-craft:
  a. Use a rail gun so the vehicle doesn't need to carry it's own fuel
  b. Fly like a conventional jet to the top of the stratosphere, then launch directly into low-earth orbit. 

5. Probing the nearest stars.  First step: build a small, unmanned probe sent by rail gun to the nearest star.  Also experiment with solar sails and ion drive (or the two in combination: capture the solar wind then redirect it into a solar-powered particle accelerator)