Sunday, July 13, 2014

Multi-borders software: reflections

It's been several weeks since I released the "multi-borders" multi-class classification software.  Along with the software, I also submitted this paper to the Journal of Machine Learning Research: Machine Learning Open-Source Software (JMLR-MLOSS) stream but sadly it was rejected.

Actually I'm quite glad that the paper was rejected as there are issues with the software, not least of which is the fact that it's not as accurate as it could be.  This is actually discussed in the paper: the eight-class test case returns an accuracy of about 56% for AGF without borders training, 54% using the "hierarchical" method (essentially a decision tree) and only 52% using the "non-hierarchical" method.  It's the non-hierarchical method that's the most interesting and that I'll be discussing here.  This uses a matrix inversion (least squares, actually) to solve for the conditional probabilities based on the "raw" probabilities from each of the binary classifiers.  That is, if P are the conditional probabilities for each of the classes and R are the differences between the conditional probabilities from the binary classifiers, then there will be a mapping, A, from one to the other and we solve the following equation in a least squares sense:

  A*P=R                    (1)

At first I thought that errors are accumulating from the estimates of the conditional probabilities, which themselves are not all that accurate.  This may not be the case.

On the other hand, you can also solve for the class through "voting" which is how most other multi-class methods work.  Arithmetically, this can be expressed by multiplying the transpose of the mapping with the "raw" classes of each of the binary classifiers, where the class is expressed as one of {-1, 1}.  This method is more accurate even when we use the difference in conditional probabilities in place of the class.  That is, we have:

  c=arg max A^T*R    (2)

where c is the class of the test point.  Unfortunately, this provides poor knowledge of the final conditional probabilities, which in the first method are very accurate. An obvious solution is to constrain (1) so that it always agrees with (2).  The least squares should probably be constrained anyway to keep the each element of P between 0 and 1 and to ensure that the sum is always 1.

In principle this doesn't look that hard: if different sets of constraints (from 1 to N, where N is the number of classes) represent sub-spaces, then it would be a matter of solving the minimization problem within progressively smaller sub-spaces until we find one that satisfies the original constraints, all the while judiciously pruning eligible sub-spaces as we go along.  Adding the new constraint brought on by the "voting" solution would complicate this procedure somewhat.  In practice, it is easy to re-normalize the results from solving (1), so they have so far been left untouched and I doubt the constrained solution would be significantly more accurate than the unconstrained.

I find it really interesting that by basicly flipping the whole equation around, we end up with something that works out about the same:

arg max A^T*R ~= arg max A^(-1)*P

No question this is related to the properties of the matrix itself and should suggest better methods of solving it.

Of perhaps even more concern is that for all the multi-class problems I've tried so far, LIBSVM has handily outperformed libAGF.  At first I thought this makes sense since AGF borders approximates a curved class border from a piece-wise collection of linear borders, while a support vector machine actually analytically warps the space so that a curved boundary is not even necessary.  But this difference is persisting even using the "raw" AGF with no borders training.  I may need to go back to the beginning to optimize the estimation of conditional probabilities.

I confess, I have been somewhat lax in testing this library.  Initially, I was content to try it on the synthetic dataset I had composed and on the particular problems I was trying to solve (discrete retrieval of humidity from satellite data and surface classification of Landsat images) because the speed advantage was just so astronomical--it seemed to make up for any other potential shortcomings such as less than ideal accuracy.  In the problems I was working on often either LIBSVM wouldn't converge or the time it took to classify the test data was so enormous as to just not be worth it.  Of course for small training datasets the speed advantage of AGF evaporates.

The LIBSVM page itself has a very nice collection of datasets. I've messed around with a few of the binary datasets in the past and in retrospect I should've documented the results more thoroughly.  That should be the rule for just about every scientific project, even casual testing.  The ones I'm currently working on are "segment" and "satimage."

Another thing to note about SVM is that it optimizes the classification error.  As you know, AGF generates estimates of the conditional probabilities.  Interestingly, the conditional probability represents the maximum possible accuracy for estimates at that particular location in the feature space.  I used this property very early on to validate the conditional probability estimates by first binning them and then comparing the actual accuracies with the averages in each bin.  Thus, in theory, classifications based on the conditional probabilities are optimally accurate, but that assumes that the estimates themselves are accurate.  Unfortunately, AGF probability estimates are are not optimized, at least not in any way that takes into account error rates.  This is something else I've been working on, mainly for probability density estimation.

Tuesday, June 24, 2014

How to work towards your own enslavement

By now I hope everyone's familiar with the privacy issues related to Google, Facebook and other internet companies.  Here is an interesting talk about it:


The most important point: what are they doing with your data?  They are building electronic models of you so that they can predict your behaviour.

If it is not yet a theorem that prediction implies control, then it should be.  This has been shown for simple systems: assuming we have good knowledge of the system dynamics, small perturbations of a chaotic system can be used to control it .  In one position I was working with the "singular vectors" of weather systems.  These are based on the integrated tangent vector and tell you in which direction, approximately, you have to perturb the system to get the biggest result.  The intended use was for prediction, but I have a bigger idea: use them to control the weather.  If I don't get to this, someone else will eventually.  We set up heat pumps and fans/turbines in strategic locations and use those to drive the system to its desired state.  Hell, they probably already use all the wind farms in Europe for this purpose.

If prediction implies control in physical systems, it is even more so in human affairs.  When I was a kid I used to play a game with my brother called, "Stratego."  It is a bit like chess, but with the conceit that the rank of all the pieces are hidden from the opposing player.  Often I feel like this is my position in life: my hand is open--I am playing chess, while the elites are playing poker.

The models they make for humans are actually a lot less sophisticated.  Mainly these are statistical models.  Statistical models that could be built, for instance, from my libAGF software.  It occurs to me I have also applied the software to the observation side of things, namely retrieving data from satellites.  Recently a fellow e-mailed me asking for help with the software.  It turns out he was rewriting the whole thing in Matlab so his company could use it without any copyright issues.  Since requesting a donation from either him or his company, I haven't heard back.

There are still so many improvements I can make on this software and at times I work daily on it.  In fact the work never ends.  At the moment I am not getting a penny for it and I'm not sure I ever did so directly.  I suspect this is part of the elite's plan as well: encourage the development of "open systems" so that they can have as much free software (and plenty of other stuff) to steal as they need.  Software that will ultimately be used for extortion, repressiong and control.  Sure, if I'm not willing to do it, there are two dozen others willing to step in to my shoes.  Sure there are already dozens, probably hundreds of other pieces of software that will do the same thing just as well.  LIBSVM and LVQ/SOMPAK are just two examples.  But I don't think I'm willing anymore to personally help brick in the walls of my own penitentiary.

Sunday, June 8, 2014

A rational ethical theory: first take

I've already mentioned my interest in ethical philosophy.  This is my first attempt to come up with a rational ethical theory:

1. An ethical statement is a statement that something is either right or wrong, good or bad.
2. An ethical system is a series of such statements.

By this definition the Ten Commandments comprise an ethical system.  The question becomes how we validate such a system, that is how do we determine its truth or falsity?  I've always been partial to the utilitarian philosophy: the greatest good for the greatest number.  In Ethics: Twelve Lectures on the Philosophy of Morality, David Wiggins makes some very pointed criticisms of utilitarianism.  For instance, imagine a situation where everyone can live well and find happiness, but at a cost: one person is excluded and lives in an extended hell.  (hmmmm... this sounds strangely familiar.)  Despite the lone sucker's nasty predicament, this would seem to fit the definition.

Apparently U.S. states with the least difference between rich and poor, people are also better off in general and this points us towards a refinement to the utilitarian principle.  Imagine happiness lying along a distribution with the x-axis being happiness and the y-axis being number of people.  The narrower and further right this distribution lies, the better.  But most important, the further right the left-most non-zero point, the better.  In other words, we need to look at the happiness of the most unhappy person.

At the time I came up with the first part, my solution was much simpler.  I tried to create an ethical system comprised of only one statement that was its own validation system.  Namely: that which increases joy is good.  Joy I decided, was synonymous with good.

The problem here is ambivalence.  We are often drawn in two directions at once.  My first, concrete example, cigarette smoking, works but it's a bit weak.  So at the risk of revealing a bit too much about myself, I was fortunate enough to have had a girlfriend who gave me a much stronger example.  A large part of human laws and taboos revolve around sex and perhaps this example will illustrate why.  (Or as Foucault puts it in The History of Sexuality, human sexuality is a particularly dense set of power relations.)  It is interesting, and perhaps a bit ironic, that I first codified the above, rather simple idea of morality while staying at a hostel in Edinburgh after having first gotten together with this woman.  Fast forward to our break-up after about a year-and-a-half of on-again off-again bickering, I found myself staying at the apartment of and even sleeping in the same bed with this woman even as she was dating a new man.  At one point, as she was about to go on a date with this fellow she started getting frisky.  On the one hand, it's hard for me to imagine anything more arousing.  On the other, I really wanted to kill this guy with my bare hands.  I cannot imagine a deeper level of ambivalence.

So this, to me, needs to be the central aspect of ethics and morality: ambivalence.  Without ambivalence, if we are always certain of the rightness of our actions and their ultimate outcome, then there is no need for ethics.

On a more general level: I would very much like to do good in the world and to leave behind something better for future generations.  I am also ambitious: I would like to be successful and to achieve many great things.  Such achievement is often quite resource-intensive and can damage the environment.  This is the crisis facing our world today.  And it should be obvious to those of us with clearer heads that the elites have mortgaged the future of our grandchildren for wealth and success today.

As the above statement suggests, there is a tendency to preference desire and pleasures.  The concept of ambivalence suggests that all desires are equal: none is higher or lower.  I know I tend to rank them into more base, "animal" desires: food, sex, personal power and prestige, revenge; and higher, more "spiritual desires": searching for truth and knowledge, fighting for justice, helping others, enjoying nature.  Ranking our desires of course is one way of resolving ambivalence.

The cancer of the Earth

Two Fridays ago I was chatting with an older fellow--a hard luck case--who had worked in the oil fields as a youth. He said some things to me that I found upsetting, not because I disagreed with them, but because I've been thinking along the same lines for some time. He said that the planet is dying and the only way out is to find another planet to kill. Oil is the blood of the planet and we a cancer upon it. The only way that we can create is by first destroying. Well, I'm not sure about oil being the blood of the Earth. Certainly it goes against much of the current scientific paradigm. One could see how it might be: the centre of the Earth is very hot and it has an iron core. Is the Earth a living thing that gains power from burning the iron in its core and oil serves as a primer? Keep in mind that Mars has a heavily oxidized surface. Is it a now "dead" planet? Shortly after he said this to me it occurred to me that scientists still don't have a very good understanding of fire and it is actually a very distinct phase of matter. As living things, we actually have more in common with flame than we do with more inert forms of matter. And a large part of what separates us from other animals is our ability to harness fire: particularly in the internal combustion engine. This, of course, is the legend of Prometheus. This fellow worked on the oil fields: perhaps he saw things that others are not privy to. I know very little about the chemistry and geology of the Earth's surface. I suspect am certain that the scientific community knows a lot less than they let on. There was a Doctor Who episode in which a group of humans on a space ship discovered that their ship was actually a giant "space whale" and to keep it moving, it was being constantly tortured. Is this the state of our modern industrial society? In the Doctor Who episode the elites were simply ignorant of the facts. Our elite, of course, would have no issue with simply lying through their teeth to cover up the facts. But I digress. Perhaps he is right about finding other planets. This might be the only way out of our current predicament. But not for the reasons you might imagine. Assuming that we don't simply send people in suspended animation or send out a spore, building a space ship to travel to another planet (and by implication another star system) would require creating, in miniature, a self-sustaining ecosystem. If we could do this inside a space ship, surely we could apply the lessons learned to make society down here on Earth more self-sustaining? I am reminded of the movie W.A.L.L.Y. The movie doesn't really work except as reductio ad absurdum. In the movie, humans have polluted the Earth to such an extent that they move out into space. The problem is, they continue in their wasteful ways while on their ship. Of course, had they continued to generate garbage at the same rate (as it shows in the movie) there would soon be nothing left of their ship. If our wasteful ways are destructive down here on Earth, the same goes out in space, only far more so.

Tuesday, April 15, 2014

How to build a super-efficient motor-assisted bicycle

The moral philosophy is a weighty topic.  Sexual politics even more so.  So here is some lighter fair about how to build a better motor-assisted bicycle.  I have already written an article about how current products are rubbish and how they are hobbled by brain-dead regulations.

An under-powered vehicle needs a lot of gears to help it adapt to different terrain and driving conditions.  Modern bicycles with derailleur gears typically have a minimum of 16 gears while hub-gear bicycles will have seven (7) or more.  Transport trucks have 12 or more gears and vehicles designed for off-road use will usually have a special gear reducer that effectively doubles the number of gears.  Contrast this with personal automobiles, which in the past, could make do with as few as three and even now rarely have more than six (6).

A lot of motor conversion kits for bicycles have a very crude transmission set-up.  One older system involved simply dropping a rubber wheel onto the front tire, but newer chain drives often aren't much better: there is only one gear and the pedals are only useful to kick-start the engine.  On the one hand, transmission requirements for human versus gasoline power are very different because the former is high-torque, low RPM (revolutions per minute) and can produce generous torque at rest, while the latter is low-torque, high RPM and cannot produce any torque at rest.  On the other hand, to save weight, the transmission ought to be shared between the two.

This is the solution I'm currently working.  First the engine.  I found this 2 hp gasoline engine, complete with magneto ignition:
The engine can drive the rear wheel through a standard bicycle derailleur gear by connecting to this Shimano front-freewheeling chainwheel from the 1980s:

Through a ratchet mechanism, the chainwheel is allowed to spin in a clockwise direction even when your feet aren't moving.  What's missing is how to connect the engine to the chainwheel but seems obvious from the photos: just chain it directly from the small sprocket mounted on the end of the engine crankshaft to the larger of the two chainrings.

There's at least three problems with this solution.  The first is that the engine achieves its horsepower peak at around 10000 rpm.  In top gear a human will have to pedal at roughly 100 rpm to travel at a speed of 50 km/h.  This implies a gear reduction of roughly 100:1!  It's not quite that bad since you don't have to be in top gear when the engine is pushing the bike at top speed.  There are multiple chainrings: potentially you could use just one very small one when the engine is engaged as long as there is still a reasonable spread.

With this in mind, notice that the chainwheels has been drilled out twice: first with a large spacing to accept this monster, 60 tooth chainring shown left and again with a smaller spacing to accept a standard 24-30 tooth "granny" ring shown at right.
The cog on the engine is 14 teeth so even using the largest rear sprocket (roughly 1:1 ratio), you get a final drive ratio of 60:14=4.29.  At maximum rpm the rear wheel will still be turning at over 2300 rpm which translates to a maximum speed of 297 km/h!

The second problem is that the engine actually spins counter-clockwise, which hints at a solution to the first problem: just have the speed reducer in one with the reverse gear.  Two gears with a tooth ratio of about 20:1 (a compound gear might be better for such a large ratio), 17:1 in combination with the giant 60 tooth ring or 14:1 with the little granny should do the trick.  If both are employed, the ratio could be as low as 10:1.

Such large ratios suggest the use of worm gears but this makes it impossible to kick or jump-start the engine with foot power or momentum and a starter motor adds unnecessary weight.  And third, we still haven't addressed the issue of engaging and disengaging the engine.  In the setup described above, the engine is always engaged making it impossible to use the pedals except for starting the engine or possibly assisting it.  This would only be acceptable for the earliest prototypes.

As a more mature, practical solution, I envision the motor being mounted beside the seat-tube with the crankshaft running perpendicular to the bottom-bracket (pedal-crank) axle rather than parallel.  Two bevel gears connect the two: a small one at the end of the crankshaft and a very large one on the outside of the chainwheel.  The engine is engaged and disengaged with a lever either by making the engine crankshaft extensible or through a pair of movable idler gears.

Another obvious essential feature of the final version will be a hand-operated clutch (foolishly illegal in the Ontario Traffic Act's definition of a moped).  Note that this will likely need to be separate from the engagement/disengagement mechanism as we don't want any extra gears or hardware connecting the pedals and creating drag while using only leg power.

If this project interests you, you can make a donation to the Peteysoft Foundation here.

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 that 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 the 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 out to a file in a crude sort of language.  Then, this 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.

Tuesday, April 1, 2014

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?