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.
Tuesday, February 28, 2017
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.
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:
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.
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.
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.
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.
Sunday, February 19, 2017
C4 for Blocker
I've missed a couple days because I'm back in Ithaca presenting my daughter to my family (they are OK with seeing me, too, but she's the one they really want to see). Anyway, that long drive behind me, I put together a C4 (Context, Container, Component, Class) diagram for my term project in Evolutionary Algorithms, which I'm calling "Blocker". (Not a particularly catchy name, especially in the Hadoop space, but I can rename it later if it really works out nicely.)
Context
Well, ya get data and ya format it so queries run fast. Not much to say on this one.
Containers
This could all be jammed into one monolith (and, I might actually do that for the class project just to reduce effort). However, it won't parallelize well unless it's properly broken into services that can run off a publish/subscribe bus. So, that's how I'm laying it out.
I also don't know if I'll actually be able to install this on non-prod at work but, it looks better to be putting something like this on industrial-strength hardware, so I'm going ahead and claiming it. A 10-node HDFS cluster is way cooler than a virtual machine running on my laptop.
Components
The data layer, ingestion, and query components constitute the bulk of the work, at least if one was to do them right. As I mentioned above, since this is just a class project for the moment, I may cut quite a few corners since they are pretty standard store and retrieve routines. I'll make sure the actual evolutionary algorithm is working before I put too much work into these.
One callout is that the Manager component in the Data Layer is actually a fairly big deal. In a space like Hadoop where you don't have commits or rollback, you have to build in quite a bit of recovery for failed tasks.
The meat of the project from the perspective of the class is, of course, the Optimize container.
The components on the left are task management so this can be properly parallelized and relegated to background status. The components on the right do the real work. The Block Generator is the most interesting piece. I haven't worked out exactly how I want to do it, but my general thought is that I'll have a prior distribution on which attributes are most significant and generate a posterior based on the performance against the logs. I'll then use the posterior distribution to generate a full set of blocks for the next generation of the repository and run the query history against that. If it performs better than the current, then that becomes the new repository. Either way, we regenerate the prior distribution and start over. The creation of new generations never stops, it should consume all the idle cycles for the cluster (or, at least, as much as gets allocated to this process - there are other processes on the cluster as well). A new generation is published only when improvement is shown, but it keeps cranking either way.
Thursday, February 16, 2017
Mind blowing
That's how my Set Theory prof described a few of the results in today's class. And, they are. Once one admits that a set can be so large that it can not even be enumerated, much less bounded, well, crazy things can happen. And, that's all good. As I've said before, sending your mind out to do battle with concepts that can't possibly be grasped is a big part of math's appeal.
But, it's also important to recognize that math is our invention. When we "prove" something in math, we're not really proving anything other than that a certain assertion is consistent with a certain set of assumptions that we made up. There's no real "truth" going on here.
The axiom of choice is just one of those things that sounds like it ought to be true, so we say that it is. If nutty results follow from that, it could be that some things are just nutty, but it could also be that the axiom of choice is nutty. Particle physicists are increasingly questioning if something as generally accepted as the "real" numbers even exists. The empirical evidence is certainly consistent with a discrete and countable version of the universe. Sure, that means that something has to be able to move from one point to another without passing through any intermediate points, but why is that such a stretch? Anybody who's ever seen a movie projector should know that it's pretty easy to trick our lame senses into assuming continuity when no such thing exists.
I'm not ready to write off the continuity of the reals quite yet, but I'll at least be man enough to admit that this whole edifice is built on sand.
But, it's also important to recognize that math is our invention. When we "prove" something in math, we're not really proving anything other than that a certain assertion is consistent with a certain set of assumptions that we made up. There's no real "truth" going on here.
The axiom of choice is just one of those things that sounds like it ought to be true, so we say that it is. If nutty results follow from that, it could be that some things are just nutty, but it could also be that the axiom of choice is nutty. Particle physicists are increasingly questioning if something as generally accepted as the "real" numbers even exists. The empirical evidence is certainly consistent with a discrete and countable version of the universe. Sure, that means that something has to be able to move from one point to another without passing through any intermediate points, but why is that such a stretch? Anybody who's ever seen a movie projector should know that it's pretty easy to trick our lame senses into assuming continuity when no such thing exists.
I'm not ready to write off the continuity of the reals quite yet, but I'll at least be man enough to admit that this whole edifice is built on sand.
Wednesday, February 15, 2017
Infinity
With the Q done, I have a chance to actually look at some of the other stuff I've done this semester. In particular, I botched one of the proofs on the first Set Theory homework rather badly. In discussing it with my professor today, I realized that it wasn't just gaps, the whole proof was plain wrong. Ah well, that's why you turn things in. Grades are secondary, it's the feedback that helps you learn.
Anyway, he suggested I give it some more thought. I did, and while I'm pretty sure you could come up with something to salvage my first effort, it's much simpler to turn things around. In general, I think that anytime you have a chance to work with finite sets, you should snatch it.
Any infinite partially ordered set contains either an infinite chain or an infinite totally unordered set.
My first attempt was to take a set that did not have an infinite totally unordered set and show that it must have an infinite chain. I did figure out how to make that work, but it's really messy. What about proving the contrapositive? That is:
Any partially ordered set that doesn't contain an infinite chain or infinite totally unordered subset is finite.
Let S be an partially ordered set that does not contain an infinite chain or infinite totally unordered subset. Let {ui} be a maximal totally unordered subset of S. Let Ui = {s in S|ui and s are ordered}. Let Um be the largest such set.
Lots of definitions so far, but all pretty straightforward. We've got a finite number of sets, and every element of S is in at least one of the sets (or {ui} wouldn't be maximal). If we can show the largest such set is finite, we're done.
Every element in Um is in a finite chain with um. Consider only the maximal chains of Um. The top element of each of those chains is either equal to or unordered with the top element of any other maximal chain (otherwise it the larger of the two could be added to the other "maximal" chain). Therefore, the top elements of all maximal chains form a totally unordered set and are must be finite in number. Remove them from Um. The remaining chains are still maximal in the diminished Um and thus the new top elements also form a finite totally unordered set. (I could introduce a bunch of new subscripts to formalize all this, but that's a pain in HTML, so I won't. Also, there is a little hand-waving here in that the claim that the remaining chains are maximal is one that really should be backed up. It's a fairly straightforward proof by contradiction that I'll leave as the proverbial "exercise for the reader"). Remove them as well. As all chains are of finite length, this process will result in an empty set after a finite number of iterations. Thus, Um is a finite disjoint union of finite sets and must be finite.
Thus all of {Ui} are finite which implies S is finite.
Note, we never claimed (though it's true) that the number of chains is finite. The trick was seeing that, as long as our collections of ordered and unordered items are finite, we have really nice properties within those collections (like, maximal elements) that make the proof much easier. The same can be said when restricting arguments to countable collections versus uncountable. Generally speaking, the only uncountable sets of interest to stats guys like myself are pretty well behaved, but I do recall a few proofs from Probability Theory 30 years ago that got mighty complicated when all edge cases were considered. I expect we'll see a few more of those as this course goes on.
Anyway, he suggested I give it some more thought. I did, and while I'm pretty sure you could come up with something to salvage my first effort, it's much simpler to turn things around. In general, I think that anytime you have a chance to work with finite sets, you should snatch it.
Any infinite partially ordered set contains either an infinite chain or an infinite totally unordered set.
My first attempt was to take a set that did not have an infinite totally unordered set and show that it must have an infinite chain. I did figure out how to make that work, but it's really messy. What about proving the contrapositive? That is:
Any partially ordered set that doesn't contain an infinite chain or infinite totally unordered subset is finite.
Let S be an partially ordered set that does not contain an infinite chain or infinite totally unordered subset. Let {ui} be a maximal totally unordered subset of S. Let Ui = {s in S|ui and s are ordered}. Let Um be the largest such set.
Lots of definitions so far, but all pretty straightforward. We've got a finite number of sets, and every element of S is in at least one of the sets (or {ui} wouldn't be maximal). If we can show the largest such set is finite, we're done.
Every element in Um is in a finite chain with um. Consider only the maximal chains of Um. The top element of each of those chains is either equal to or unordered with the top element of any other maximal chain (otherwise it the larger of the two could be added to the other "maximal" chain). Therefore, the top elements of all maximal chains form a totally unordered set and are must be finite in number. Remove them from Um. The remaining chains are still maximal in the diminished Um and thus the new top elements also form a finite totally unordered set. (I could introduce a bunch of new subscripts to formalize all this, but that's a pain in HTML, so I won't. Also, there is a little hand-waving here in that the claim that the remaining chains are maximal is one that really should be backed up. It's a fairly straightforward proof by contradiction that I'll leave as the proverbial "exercise for the reader"). Remove them as well. As all chains are of finite length, this process will result in an empty set after a finite number of iterations. Thus, Um is a finite disjoint union of finite sets and must be finite.
Thus all of {Ui} are finite which implies S is finite.
Note, we never claimed (though it's true) that the number of chains is finite. The trick was seeing that, as long as our collections of ordered and unordered items are finite, we have really nice properties within those collections (like, maximal elements) that make the proof much easier. The same can be said when restricting arguments to countable collections versus uncountable. Generally speaking, the only uncountable sets of interest to stats guys like myself are pretty well behaved, but I do recall a few proofs from Probability Theory 30 years ago that got mighty complicated when all edge cases were considered. I expect we'll see a few more of those as this course goes on.
Tuesday, February 14, 2017
Non-circular
We were given a pseudo-assignment (not turned in or graded, but something we are supposed to do before class to facilitate discussion) in Set Theory to show that Weak Induction, Strong Induction, and Well-Ordering of the Naturals is all the same thing. That is, if you're given any one of them, you can prove the other two without any other axioms.
The logic isn't particularly complicated, but it is very hard not to get into circular arguments. The three assertions are so similar (especially Weak and Strong Induction) that you can easily end up proving what you started with or assuming what you were trying to prove.
For example, here's a proof of Strong Induction using Weak Induction to show that the conditions of Strong Induction imply the conditions of Weak Induction and therefore the conclusion of Weak Induction (!)
First, let's state what we're given, Weak Induction:
Let R be a subset of the Natural numbers {1, 2, 3, ...}. If
The logic isn't particularly complicated, but it is very hard not to get into circular arguments. The three assertions are so similar (especially Weak and Strong Induction) that you can easily end up proving what you started with or assuming what you were trying to prove.
For example, here's a proof of Strong Induction using Weak Induction to show that the conditions of Strong Induction imply the conditions of Weak Induction and therefore the conclusion of Weak Induction (!)
First, let's state what we're given, Weak Induction:
Let R be a subset of the Natural numbers {1, 2, 3, ...}. If
- 1 is an element of R and
- n is an element of R implies n+1 is an element of R
then R is the Natural numbers.
Now, what we're trying to show (renaming the conditions and the set, which should help keep them straight), Strong Induction:
Let S be a subset of the natural numbers. If
- 1 is an element of S and
- {1, 2, ..., n} is a subset of S implies n+1 is an element of S
then S is the Natural numbers.
We're going to show this by using Weak Induction twice. First to show that the conditions of Strong Induction imply the conditions of Weak Induction, and then to claim the result.
Obviously A implies 1 (they're the same thing).
Now, it gets harder to follow. It seems like B would necessarily imply 2 (it does, but we can't just claim that; we have to prove it). B requires that all the elements less than or equal to n be in S whereas 2 only requires that n be in R. So, rather than immediately claim the result, we have to show that it if n is in S, so is every other natural number less than n. Only then can we claim that 2 holds and use Weak Induction. The reason this argument gets hard to follow is that we prove this intermediate step using Weak Induction.
For n=1, we have that {1} is a subset of S by A.
For n≥1, we assume that {1, ..., n} is a subset of S. By B, we then know that n+1 is in S. Thus, {1, ..., n+1} is a subset of S. Therefore, by Weak Induction we have that {1, ..., n} is a subset of S for all n in the Natural numbers. If that is true, then both the condition and conclusion of 2 is true for all n in the Natural numbers and we have shown that A and B imply 1 and 2.
Therefore, S meets the conditions of Weak Induction and must be the complete set of Naturals.
That sure seems like a lot of work to show something that's pretty obvious. And, it is. But, Mathematics got in a whole pile of trouble a couple centuries ago by assuming too many things that seemed obvious in countable cases which then turned out to be very false when applied to more general sets. Rigorous proof is not an adequate defense against such things as there are some very real limits to logic, but, it's definitely the safer way to go.
We're going to show this by using Weak Induction twice. First to show that the conditions of Strong Induction imply the conditions of Weak Induction, and then to claim the result.
Obviously A implies 1 (they're the same thing).
Now, it gets harder to follow. It seems like B would necessarily imply 2 (it does, but we can't just claim that; we have to prove it). B requires that all the elements less than or equal to n be in S whereas 2 only requires that n be in R. So, rather than immediately claim the result, we have to show that it if n is in S, so is every other natural number less than n. Only then can we claim that 2 holds and use Weak Induction. The reason this argument gets hard to follow is that we prove this intermediate step using Weak Induction.
For n=1, we have that {1} is a subset of S by A.
For n≥1, we assume that {1, ..., n} is a subset of S. By B, we then know that n+1 is in S. Thus, {1, ..., n+1} is a subset of S. Therefore, by Weak Induction we have that {1, ..., n} is a subset of S for all n in the Natural numbers. If that is true, then both the condition and conclusion of 2 is true for all n in the Natural numbers and we have shown that A and B imply 1 and 2.
Therefore, S meets the conditions of Weak Induction and must be the complete set of Naturals.
That sure seems like a lot of work to show something that's pretty obvious. And, it is. But, Mathematics got in a whole pile of trouble a couple centuries ago by assuming too many things that seemed obvious in countable cases which then turned out to be very false when applied to more general sets. Rigorous proof is not an adequate defense against such things as there are some very real limits to logic, but, it's definitely the safer way to go.
Monday, February 13, 2017
Forward
With the Q (and a few days of recovery) behind, I'll get back to regular posts. Here's the plan for this spring:
- MA5140 - Set Theory. This is pretty deep water. The class is a mix of Masters and PhD students and there's a significant gap between those two groups at UMSL. This material isn't particularly relevant to my thesis, but it's stuff I really like, so I plan on considering all the material, even if most of the class has to stay closer to shore.
- CS5320 - Evolutionary Computing. This could have been a pretty easy class had I not decided to include a substantial piece of my thesis work as the term project. As I did do that, I expect this to be a very time consuming class. Things that need to be developed:
- Update the data layer from CISS (my stratified query algorithm that may or may not get published) to do a better job of managing attributes in a block.
- Update the query engine from CISS to use the enhanced attribute information to determine if a block contains any rows in a query (and ignore it if it doesn't).
- Collect and store statistics on query patterns and block usage for each pattern.
- Build a test harness that can submit several thousand queries against the data using patterns that vary over time.
- Build a data ingestion program that sorts new data into blocks based on block preferences.
- Design an evolutionary algorithm that determines optimal block preferences.
- Implement the above algorithm and call it from the ingestion program.
- Build a secondary test harness that drives the block deletion/re-ingestion strategy between sessions of query harness.
- Write up the results and present to the class.
- Each of the above tasks is what we would call a 3-5 point story at work, meaning that a competent developer should be able to get it done in around a week. There are 9 stories in the list. There are 12 weeks remaining in the term. Oh, yeah, I have a day job, too. Seems I'll be busy. I may be able to cut the scope a bit and still have a good project and something useful going forward.
- Fortunately, I don't have any other school obligations for this semester. My adviser does seem to have renewed interest in getting CISS published, but that paper is pretty much ready to go. The term project for CS5320 will constitute adequate progress against the thesis.
- Also fortunate is that spring is the less nutty time at work, so I can take a few days off here and there if needed. I also don't much care how fast I run Boston, so running will simply be a fun thing to do without the stress of having to get in productive workouts.
Saturday, February 11, 2017
Failure points
Let me open by acknowledging that I do not yet know for sure that I passed the Q. I'll be pretty surprised if I didn't, but the decision is the faculty's, not mine. That said, let's suppose I passed the Q. What now remains between me and a PhD?
1) The admission to candidacy (also known as the "A" exam). This is an oral exam where you pitch your thesis idea. This doesn't intimidate me in the least. I pitch project ideas all the time at work. They typically carry 7-digit price tags. Selling a research direction which will cost the faculty exactly zero dollars and zero cents doesn't seem like much of a stretch. Sure, you still need to make sure it's worthy stuff. My point is that I'm used to having to justify my work. And I don't mean vague ideas about work. I'm a consultant. If I don't justify my actual work in very specific terms, I'm fired. Period.
2) Finish my credit hour requirements. Since the faculty seems willing to transfer all my Masters credits from Cornell, this will basically happen at the end of this term. I'll probably take one or two more courses along the way simply because they are relevant and/or interesting, but I could actually finish out on just thesis research if I wanted to.
3) Write a dissertation. This is a ton of work, but, that's all it is: work. I'm used to work.
4) Thesis defense (also known as the "B" exam). I'm sure it happens, but I don't know anybody who failed their thesis defense. If your adviser is at all competent, you shouldn't get past the previous step until this one is a gimmie.
5) Address issues from defense. Again, work, except this time it's particularly well-defined work. There are specific issues that you need to address. You address them. Not a problem.
My point is that, while thousands of people abandon the quest while "ABD" (All But Dissertation), the reality is that, for someone like me who generally doesn't quit simply because something is long and difficult, the Q was the failure point in the whole PhD operation. Now, it's just a lot of work.
It's time to get to work.
1) The admission to candidacy (also known as the "A" exam). This is an oral exam where you pitch your thesis idea. This doesn't intimidate me in the least. I pitch project ideas all the time at work. They typically carry 7-digit price tags. Selling a research direction which will cost the faculty exactly zero dollars and zero cents doesn't seem like much of a stretch. Sure, you still need to make sure it's worthy stuff. My point is that I'm used to having to justify my work. And I don't mean vague ideas about work. I'm a consultant. If I don't justify my actual work in very specific terms, I'm fired. Period.
2) Finish my credit hour requirements. Since the faculty seems willing to transfer all my Masters credits from Cornell, this will basically happen at the end of this term. I'll probably take one or two more courses along the way simply because they are relevant and/or interesting, but I could actually finish out on just thesis research if I wanted to.
3) Write a dissertation. This is a ton of work, but, that's all it is: work. I'm used to work.
4) Thesis defense (also known as the "B" exam). I'm sure it happens, but I don't know anybody who failed their thesis defense. If your adviser is at all competent, you shouldn't get past the previous step until this one is a gimmie.
5) Address issues from defense. Again, work, except this time it's particularly well-defined work. There are specific issues that you need to address. You address them. Not a problem.
My point is that, while thousands of people abandon the quest while "ABD" (All But Dissertation), the reality is that, for someone like me who generally doesn't quit simply because something is long and difficult, the Q was the failure point in the whole PhD operation. Now, it's just a lot of work.
It's time to get to work.
Friday, February 10, 2017
Optimal Prep
Obviously, one doesn't just decide to "take the Q" in a vacuum. That decision could only be made in the context of a lifetime of learning in the field of study. Similarly, while one might decide on a whim to "run a marathon", one cannot expect to run one competitively without years of development already in the bank. It is with that context in mind that I present the rather interesting similarity:
Goal: Pass PhD Qualifying exam (a varying standard, for sure, but measureable so it meets the criteria for a goal).
Training horizon (when training became specifically targeted to the event): 6 months
Preparation time: 245 hours
Average per day: 1.5 hours
Maximum per day: 6 hours
Time of event: 5 hours
Result: most likely success, though the official word is pending.
Goal: First sub-3 Marathon
Training horizon: 5 months
Preparation time: 235 hours
Average per day: 1,7 hours
Maximum per day: 5 hours
Time of event: 2:58:48
Result: success (Wineglass 2010)
It's enough to make you wonder if maybe the human organism is simply wired for success over a 6-month training horizon.
Goal: Pass PhD Qualifying exam (a varying standard, for sure, but measureable so it meets the criteria for a goal).
Training horizon (when training became specifically targeted to the event): 6 months
Preparation time: 245 hours
Average per day: 1.5 hours
Maximum per day: 6 hours
Time of event: 5 hours
Result: most likely success, though the official word is pending.
Goal: First sub-3 Marathon
Training horizon: 5 months
Preparation time: 235 hours
Average per day: 1,7 hours
Maximum per day: 5 hours
Time of event: 2:58:48
Result: success (Wineglass 2010)
It's enough to make you wonder if maybe the human organism is simply wired for success over a 6-month training horizon.
Thursday, February 9, 2017
Q-1
Well, tomorrow is the day. I wouldn't say that I've prepped optimally, but I believe I am optimally prepped. By that, I mean that, while I could have done things better, the end result is about as good as I could hope for. The reality is that a 53 year old brain does not retain information as well as a 23 year old brain. Compound that with the fact that, unlike 30 years ago, I've got lots of other stuff that simply can't be ignored and it's just not realistic to expect to go into this matching the prep that a "traditional" grad student would bring.
Will it be enough? I don't know and, honestly, I'm beyond stressing over it. I'm numb. I'll take my best shot and if that's not good enough, I'll get on with a new vector in life.
Will it be enough? I don't know and, honestly, I'm beyond stressing over it. I'm numb. I'll take my best shot and if that's not good enough, I'll get on with a new vector in life.
Wednesday, February 8, 2017
HW
Still prepping for the Q. If you simply can't live without some math content here, you can put yourself to sleep reading my first assignments in each class this term.
Set Theory
Evolutionary Computing
Set Theory
Evolutionary Computing
Tuesday, February 7, 2017
Contrast
I probably should have left my concentration as Computer Science. I could pass the Q in that without even studying. That said, nights like tonight make me glad I switched to Stats (though maybe I should have gone all the way to Applied Math since it's the Stats questions that seem to be tripping me up the most).
So, in Set Theory, we had a wonderful discussion of some of the deepest ideas ever contemplated. The centerpiece was the continuum hypothesis proposed by Cantor. It states that there were no cardinal numbers between the countability (the naturals) and continuity (the reals). It seems like the kind of thing that would either be true or false. No deals. In the ensuing 150 years it has been tackled by the best and brightest and two things have been demonstrated: 1) you can't disprove it (Godel, 1938) and 2) you can't prove it (Cohen, 1963). It's either an axiom or a curiosity, but it doesn't follow from anything.
Skip down the hall to Evolutionary Computing. Another good lecture, but the centerpiece of this one, Quantum Selection, is the biggest pile of baloney since Donald J Trump last opened his mouth.
Sorry CS dudes, you may make the big bucks, but the math folks are waaaaay smarter than you.
So, in Set Theory, we had a wonderful discussion of some of the deepest ideas ever contemplated. The centerpiece was the continuum hypothesis proposed by Cantor. It states that there were no cardinal numbers between the countability (the naturals) and continuity (the reals). It seems like the kind of thing that would either be true or false. No deals. In the ensuing 150 years it has been tackled by the best and brightest and two things have been demonstrated: 1) you can't disprove it (Godel, 1938) and 2) you can't prove it (Cohen, 1963). It's either an axiom or a curiosity, but it doesn't follow from anything.
Skip down the hall to Evolutionary Computing. Another good lecture, but the centerpiece of this one, Quantum Selection, is the biggest pile of baloney since Donald J Trump last opened his mouth.
Sorry CS dudes, you may make the big bucks, but the math folks are waaaaay smarter than you.
Monday, February 6, 2017
23
... years of marital bliss. Well, that's overstating things a bit, I suppose. However, given how easy our legal system makes it to walk out on a marriage, I think 23 years is a pretty good indicator that both parties are pretty positive on the arrangement.
Our actual anniversary was yesterday, but between celebrating that, going to church, and attending a Super Bowl party, I didn't have much time to write. Astute readers will note that I haven't been writing much of anything in this blog lately. That's because I've been writing a whole lot of solutions to math problems on paper. Enough so that I've given myself a mild case of carpal tunnel syndrome. Kate gave me her wrist brace which seems to be helping quite a lot.
Five days to go until the Q.
Our actual anniversary was yesterday, but between celebrating that, going to church, and attending a Super Bowl party, I didn't have much time to write. Astute readers will note that I haven't been writing much of anything in this blog lately. That's because I've been writing a whole lot of solutions to math problems on paper. Enough so that I've given myself a mild case of carpal tunnel syndrome. Kate gave me her wrist brace which seems to be helping quite a lot.
Five days to go until the Q.
Thursday, February 2, 2017
Lets Go Blues
Kate thinks I'm over-preparing for the queue. I'll agree I'm over-stressing, but I don't think I'm over-preparing. Anyway, it's been a long week at work and there really isn't a whole lot of new information I'm going to digest in the next six days, so I took Yaya to a hockey game. It was her first NHL game.
Sellout crowd and Blues won 5-1. Made for a fun evening.
Sellout crowd and Blues won 5-1. Made for a fun evening.
Subscribe to:
Posts (Atom)