Tuesday, February 28, 2017

Evolutionary Algorithms HW2

is here.

Not due until Thursday, but the prof doesn't seem to mind people working together on it, so I don't see any harm in publishing it.


Monday, February 27, 2017

Sunday, February 26, 2017

Smart versus brilliant

I've been pretty sick this last week (a rarity for me, but it happens) and have already taken a couple days off for rest. As a result, I'm working through the weekend. Between the sickness and driving to and from NY to visit my parents, I did have plenty of time to think about various things.

One idea that I kept coming back to was how our education system is so biased towards making kids smart. That sounds like a pretty good thing. The point (or, at least, a significant aim) of education is to make you smarter, right? The rub is that there's a small percentage of kids who simply don't operate that way. They function on brilliance. Both techniques work, but they are not at all the same thing.

Smart, as I am using it here, means learning enough factual information that new problems are easily solved by fitting them into an existing framework. You need to divide 426 by 19. You've never done that before. But, you know how to do long division. There's no need to be afraid of that problem.

All well and good, but a brilliant kid won't likely use long division (unless forced, and then they'll probably mess it up). They'll just look at the numbers and say, "around 22". If pressed, they might look at the ceiling for a few seconds and say, "OK, a little more than 22." I'm not talking about idiot savants, here. A person who can immediately compute that 426/19 = 22.421 is a whole 'nuther thing. I'm just talking about normally intelligent kids who don't solve problems in a linear fashion.

If you ask the brilliant kid how they got that, they may have real difficultly explaining it. They probably don't know themselves. When I cooked up that example, I tried to follow my own thought process in answering it. It went something like this: 20x20=400. That's about the same as 19x21, I need at least 1 more. 22.something. It's actually very similar to how Genetic Algorithms solve optimization problems. Start with an answer that's certainly wrong but probably in the ballpark and then mess with it until it works.

The important thing to note is that it's not an algorithm. It's guessing. Unlike long division, I have no guaranteed path to success. I'm just poking at the answer until it reveals itself. Sometimes that doesn't work very well, but usually it does.

Now, you could certainly argue that, unlike a GA running on a computing grid that tries thousands of possibilities in a second, a person is going to have a mighty hard time getting 22.421 through trial and error. I would counter that by saying that there are almost no situations outside of finance or engineering where more than three significant digits are required. And, if you're doing finance or engineering by hand calculation, you are one of the world's truly great time wasters. That's what calculators are for.

Some educators seem to have grasped that these other "techniques" have merit and tried to work them into the curriculum. Unfortunately, they are being taught using the "smart" paradigm. That's a complete disaster. If you're going to go the smart route (and that is the way to go for the vast majority of kids), you need techniques that are trustworthy. A small, but effective repertoire of skills is far more useful than a vast array heuristics that may or may not help in any given situation.

If you're going to teach these things at all, they need to be taught as brilliancies. Honestly, I'm not really sure how you do that. Nobody every taught me and every other person I know who's comfortable doing rough arithmetic in their head also developed their techniques on their own. I think the best you could do is encourage guessing and substitution as starting points and the kids who like that approach will figure out how to use it. For everybody else, long division works just fine.

The sad part about all this is that, in trying to broaden the curriculum, they've made it even harder for kids to find their way through it. Yaya was completely bowled over by all the tricks she was being taught in elementary school. She was fine with just following steps, but if she had to actually pick which steps to apply, she got lost quickly. And, if she picked one that made the problem harder rather than easier, she was very quickly frustrated.

Meanwhile, I don't think this is helping the brilliant kids one bit. Having to actually show their steps slows down the intuitive leaps that make the whole guess and adjust process work so well.

You might derive from my choice of words that I think brilliant is better than smart. I don't. I just used those words because they seemed to fit. As both approaches work, I don't see why either should be more than a preference. My concern is that, by trying to present brilliant as smart, that preference becomes less obvious and kids are just getting confused. Most sort it out, of course, but some don't. I personally know of at least two kids who are seriously struggling in Middle School math right now solely because it was presented to them so badly in Elementary School.

Saturday, February 25, 2017

Not in Kansas anymore

As I read the following proof in my Set Theory text, I was reminded of Dorothy's line to Toto. I won't even state what's being proven, because the weirdness of the proof is greater without context:

Obviously, e ≤ d + e. By Theorem 9 it will suffice to prove that d + e ≤ e. Now d + e ≤ e + e, and by Theorem 13, e + e = e.
OK, if you were to throw that at a High School kid, they'd give you the first sentence and then say you're full of crap. An industrious Undergrad might conclude that d and e are both zero. In fact, the opposite is true. We have left the familiar realm of finite numbers and are now dealing with different levels of infinity: the cardinal numbers. It's wierd stuff, but again, you just go with it and it all works.

Incidentally, if you came away from my previous post on the axiom of choice thinking that you can just dismiss this stuff as mathematical musings, you missed my point. Yes, these are human constructs and nature doesn't have to play that way (and it's quite possible that it doesn't). But that doesn't make them irrelevant, either.

Consider the Naturals, {1, 2, 3, ...}. Everybody agrees that the Naturals are just that, natural. There's even a famous (by math standards) quote: "God created the Natural numbers, everything else is the work of man." by Leopold Kronecker (1823–1891). The point is, counting is as real as math gets. So, what happens if you take the power set of the naturals, that is every possible subset of them. How many subsets of the Naturals are there? Hells bells, the cardinality of that set is c, the continuum. The same as the Real line. All you've done is acknowledge that you might want to look at subsets of the most obvious thing out there and you're already into uncountable sets and all the craziness that comes with them.

Friday, February 24, 2017

QGA

I may have been a bit hasty in my dismissal of Quantum Genetic Algorithms. Having now read a bit of background literature, I'll concede that it's at least worth investigating. Unfortunately, it's hamstrung by the fact that the Quantum Computer does not yet exist. And a simulated QGA is pretty lame. The papers I've seen that claim faster convergence are cheating: they aren't counting all the extra computation complexity in simulating the quantum registers. If you applied the same effort to some sort of probabilistic crossover scheme, I'm quite sure you could get the same convergence rates.

That's not to say that simulating it is a bad idea. Charles Babbage's computing engine never really worked, but Ada Lovelace's programs written for it laid the groundwork for imperative programming decades before they could be practically applied. Given the accelerating pace of hardware advances, it makes some sense to get a jump on things because the quantum computer will show up one of these days; probably sooner rather than later.

But, until that day comes, we're stuck with deterministic computing and throwing a sheet over it and calling it something else is less than intellectually honest.

Thursday, February 23, 2017

Q-over

I've been super sick the past couple days and still am feeling pretty bad. One piece of good news: I passed the Q. I was pretty sure I had, but it's always nice to know for sure. I'm now into uncharted waters as this is the point at which I decided to leave Cornell. That doesn't intimidate me any, but it does mean I should probably do a bit more listening to what the faculty has to say about my progress. Up until now, I've been pretty much keeping my own councel.

Monday, February 20, 2017

NP Complete?

While the term assignment doesn't require the question be answered (or even acknowledged), any application of an Evolutionary Algorithm should be preceded by at least considering if it wouldn't be better to solve the problem directly.

The question is particularly relevant in my blocking problem because, right now, direct solution is pretty much the way it gets done. Non-optimal, for sure, but direct. Partitioning is either determined up front by the database designer or created after the fact in the form of aggregations. The former is almost never done by rigorous analysis; it's more the database designer's intuition. The latter may also be specified by the designer. If not, dynamic aggregations are built in response to query patterns. This last bit is the closest to what I'm proposing, but I'm trying to do it without losing the granularity of the data.

At any rate, none of the above "direct" methods constitute algorithms because the resulting solutions are just a good crack at the best solution. Nobody claims they are actually optimal.I'm not making any claim of optimality, either, so that state of affairs needs to be justified. The simple answer is that it's hard. In the world of optimization theory, that means NP-hard. NP-hard is generally accepted to mean that you can forget about solving it exactly on large data sets (this assertion is unproven, but even if it's turns out that they can be solved in polynomial time, it's a polynomial that very quickly gets bigger than anything an existing machine can handle).

The usual strategy for showing that an optimization problem is NP-hard is to show that the corresponding decision problem is NP-Complete. That is, that every other NP-Complete decision problem can be decided by an algorithm that solves this one (if such an algorithm existed). Fortunately, as this operation is transitive, you only have to find one and they all fall into line.

So, which one? And, more fundamentally, what is the corresponding decision problem?

Starting with the second question, the optimal solution is one that minimizes the number of blocks that have to be read to satisfy a finite set of queries. The corresponding decision problem is, "Does there exist a solution in which exactly k blocks need to be read?"

Given that, what known NP-Complete problem can be beaten into a form that solving this problem would also provide a solution to it? That's going to take some thinking. The one that looks most promising to me at first glance is Steiner Trees, one the original 21 NP-Complete problems proposed by Karp in 1972.

The Steiner Tree problem tries to connect terminal vertices in a graph with a tree having a given total edge weight. It seems there might be a way to frame that with each tree node being a partitioning attribute, the terminal nodes being the blocks, and the edge weights being how often the partitioning attribute(s) don't allow you to quit traversing the tree.

Another possibility would be to frame it as a Linear Programming problem since all of those are known to be NP-Complete. You have to be careful with that, though. It's fairly clear that you could solve this using Linear Programming, but you can solve lots of easy problems using Linear Programming. That just proves that the problem is NP-easy (as in, no harder than NP). To show it's NP-hard, you have to do the opposite: show that any Linear Programming problem can be solved by solving your problem.

Again, not needed for the class project, but definitely worth pondering if it's going to become part of my thesis.