Monday, February 8, 2010

It's A Small World (network) After All

Certain ideas have a way of showing up wherever you look. The Golden Ratio appears again and again in art and nature. Chaos Theory becomes integral in just about any interesting real world process. It seems like every time I hear about small-world networks, it's in a new context. You've probably heard of it as well, at least in terms of Kevin Bacon.

Small-world ends up being an apt description of this phenomena in two ways. First, any two members of the network are "close", in that just a few connections link them. Hence the game Six Degrees of Kevin Bacon, where in fact 4 degrees are unusually distant (an interesting tidbit from the Wikipedia page: Kevin Bacon doesn't make the top 100 list of most central actors. The top billing shifts as new movies are made, but at the time of this posts is held by Dennis Hopper).

Small-world networks also have "clusters", where individual nodes tend to form groups that are more likely to connect internally than externally. Certain directors regularly use the same actors. An even more clear example is your own social network: you're probably a member of a couple friend groups, where everybody knows everybody else. Hence the entire world is small (compact), but it's also made up of lots of small worlds (clusters).

Why do small world networks matter? We're not exactly sure. There are theories that it's because they're more robust to damage (dropped nodes or edges). Alternatively, it could be that the rules that lead to them (e.g., preferential connection to already large nodes) are common, unrelated to any desirable network property. But although the reason is up for debate, they show up so often something must be up. The interactions between your genes, some ecological systems, brain structure, rock fractures, and social networks are all small world networks. As graph theory spreads through more fields of science I suspect many more examples will be found.

I'm sure I'll post about small networks again, as their tendency to pop up everywhere makes them a good tool for understanding the connections between disparate fields, but I'd like to use them in this post to talk about jobs. I don't have any empirical evidence this is so, but I suspect people's ability to take a job forms a small world network. There are definitely hubs: lots of people are qualified to work at Wal-Mart. There are certainly clusters: Aerospace Engineers could replace each other, but not many other people could. Is the network compact? That's precisely my concern, it appears to be spreading out. If nature finds small world networks to be so important, is that safe?

Let's assume some salesmen know a field really well, and some can just pitch anything. Let's assume the ones who know that field really well could move into some other aspect of it, like management. Let's consider a world where the car industry is declining, and robotics is really catching on. The competition for the sales jobs in the car industry is going to increase, and commissions will be shrinking. Meanwhile, the growing robotics field is likely in need of more workers, so salaries will be comparatively high. Those deeply enmeshed in the automotive world are stuck, but the universal salesmen will move on to greener pastures. As salesmen flow into robotics, the situations are likely to stabilize, and now that the demand is met, salaries will start declining again. Since managing a robotics plant might not be as transferable a skill as sales, that aspect of the field will still be in demand: the sales guys who know robotics well will have the opportunity to move into management. Thus there's a net flow from car sales into robot plant management, even though none of the car salesmen were qualified for that position. A small world network means that indirect actions can still be very powerful. If 10 people needed to each switch jobs to transfer personnel from one field to another, the mechanism would be far too slow and weak to be meaningful.

When everyone was farmers, the only limits for job replacement were geographic in nature. As occupations require greater and greater skill and training, we appear to be breaking into clusters. The highly educated can move within a couple fields, although not universally. Additionally, these fields may be clustered, so aerospace and pharmacology might be high skill but weakly linked. Meanwhile, large portions of the population lack the education for any of these technically challenging fields, and so are stuck in there own cluster. As certain fields declining (see, e.g. Detroit), there isn't the same opportunity to move that labor indirectly to cutting edge fields like nanotechnology: the path from assembly line worker to materials scientist is too long and one directional. You'd expect, then, the very universal hubs of entry level positions would get inundated, as that's the common direction from all the declining industry. The competition between the young and old for jobs suggests that's exactly what's happening right now.

Could the recession be partially our economy diverging from small world principals? It's something I lack evidence for, but that's worth considering. The economy may be becoming resistant to change at the same time the uncertainty about the future is growing. It's an interesting thought as well, because it suggests that this is something we could measure and take specific actions to address. Some fields are inherently high-skill, but some can be achieved by either. Farming is increasingly done by small groups of scientists. They're more likely to be able to switch to other important fields, and farming can clearly be done as a human labor intensive activity, so a transformation towards smaller farms might help keep the system more compact (and farming has arguably held this role since civilization form). It also suggests that opportunities for workers to get new training, and broad, cross-discipline degrees would help. The auto industry probably become a bigger hub as other manufacturing industries closed their doors: if we'd seen that more and more people were concentrating in a single industry we could tried to promote new links between it and other fields, or otherwise prepared for the coming problems. I'm interested to see how network gets applied to this and other problems, as it has the potential to help us understand underlying problems before they surface or at least to connect symptoms to a cause.

Saturday, February 6, 2010

The Limits of Knowledge, Part III

(Continued from parts I and II)


Kurt Gödel (1906-1978)


I left off last time with Bertrand Russell and Alfred Whitehead trying to derive all of mathematics from a small set of logical axioms, preserving consistency and completeness in the process. A consistent mathematical system will always give the same answer to the same question. 1+1 = 3 doesn't occasionally turn out to be true. It's always false. Completeness says that if you can form a valid mathematical statement, you can derive whether it's true or false in your system.

It's easy to see why math being inconsistent would be problematic: You can never be confident about anything again. 1+1 might equal 3. The oven might start shooting out cold air. The Earth could disintegrate at any moment. Who knows? Any argument against even the craziest idea is ultimately based on logic, and that could always change.

An Incomplete Mathematics is less worrisome, but it would upend the scientific and mathematical philosophy of much of history, dating back at least to Greece. We were often seen either as being guided explicitly by divine forces, or as the only logical outcome to a specific setup of the universe. Truth was viewed as a platonic beauty: every statement is true or false. You may not be able to figure it out, but in theory it could be figured out. At the very least God must know the answer. But if all mathematics and logic are incomplete, then there are meaningful, interesting questions without answers. For the divine to be all knowing he'd have to be inconsistent. Which is arguably his prerogative, but it's a very different world. It's not that any path towards truth would be doomed to failure because of your human limitations, any path towards truth would be inherently doomed to failure. No such path could possibly exist. It's a much more pessimistic understanding of the world.

And fittingly, a very pessimistic individual proved that no formal system can be both consistent and complete. It seems common for ideas that upend fields to come from the periphery, from the marginalized groups of scientists. Einstein was unable to find work within the physics community before he revolutionized our understanding of the universe. While Kurt Gödel did his work from within the field of logic, he was inherently an outsider. One of my favorite anecdotes about Gödel revolves around his dislike of human interactions. When someone would try to schedule a meeting with him he would oblige, making explicit plans to meet at a particular location at a particular time and date. Gödel would never show up. When asked why he made all those appointments he had no intention of keeping, Gödel answered that it was the only system he'd found that stopped people from persisting in trying to meet him.

Russel had found a paradox in Frege's attempt to formalize mathematics, so he constructed elaborate rules to keep those paradoxes out. If in doing so he introduced new paradoxes, he'd invent new axioms to hide those. G
ödel proved that any attempt to remove paradoxes just added new ones. It's a tricky bit of math, but it comes down to the idea that any interesting formal system can construct a statement along the lines of "this statement is false". Any system that can't make that statement in some form is too restricted to do anything more interesting than addition in. Gödel didn't just prove paradoxes existed in some system, he proved they'll exist in any system. Mathematics is filled with infinities of paradoxes, and there's nothing you can do about it.

G
ödel grew less stable as he aged, eventually become extremely paranoid of both germs and poison. He refused to eat anything unless his wife tasted it first. When she was hospitalized for six months and suddenly unable to serve this role, Gödel starved to death. It was an odd end for such a monumental mathematician. Gödel's Incompleteness Theorem is one of those truths so fundamental to the universe, it's unlikely his name will ever be forgotten as long as man exists. It's not the most exciting theorem, but it conclusively set down limits to knowledge, a concept that would be extended with the advent of computers.

Saturday, January 30, 2010

Carrots, Sticks, and Carrot Sticks

I'm always slightly amused by debates about whether to use a reward or a punishment to promote certain behavior. For example, should Massachusetts encourage universal health care by fining people who aren't covered (as they do now), or should they give people who are covered a tax break? Should Jimmy get a trip to Disney if he passes all his classes, or should we cancel the family vacation to Disney if he fails?

I think the second example demonstrates why I find the reward/punishment dichotomy amusing. It's often just semantics. If Jimmy gets passing grades, then he'll end up in Disney. If you don't have health insurance, then you'll shoulder more of the Massachusetts tax burden. Some punishments are clearly punishments (imprisonment), some rewards are clearly rewards (a trophy), but especially when dealing with large groups, you're redistributing some benefit/cost, not explicitly rewarding or punishing.

It seems to come up in taxes a lot. Taxing a segment of the population is unpopular, giving tax cuts to another group are fine. So rather then punish polluting firms, you reward non-polluting firms. Rather then tax increases for the poor, you cut the taxes for the rich and let inflation bring things back to a balance. Amazingly, wording something as a reward or a punishment can make all the difference.

Thus I propose a new term in the vein of "carrot and stick" already used to differentiate between rewards and punishments (as an aside, inaccurately. The term probably comes from tying a carrot to a stick to lead an animal, not beating it while feeding it to a tasty treat). "Carrot" is a reward, "Stick" is a punishment, and "Carrot Stick" is a case where it's both. You can feed a carrot stick to your donkey, or you can hit him with it (possibly ineffectually, but it's a metaphor). What a versatile tool those pre-cut veggies are!

Sunday, January 24, 2010

The Limits of Knowledge, Part II

(continued from Part I)

Bertrand Russell (1872-1970)

One way of ensuring your name will always be remembered is to have some important scale or number named after you. Slightly less surefire, but still valid, is to make a prediction so fundamentally wrong that people will delight in repeating it generations later. Lord Kelvin passes on both accounts with the Kelvin temperature scale and this (possibly apocryphal) quote: "There is nothing new to be discovered in physics now; All that remains is more and more precise measurement." Five years later, Einstein would publish his paper on Special Relativity.

I bring this up to point out the scientific and mathematical philosophy of the 19th century. Both were progressing at unprecedented rates, and it seemed possible that man would master all their secrets. With each scientific success, people believed that some fundamental truth was coming closer. Quantum Mechanics deals with a fundamental indeterminacy in the universe (see Schrödinger's Cat), but Newtonian physics is theoretically solvable. If you know the position and velocity of each particle you can predict the future as far forward as you care to. There was a novel philosophy growing that man wasn't a creature of free will, or a Calvinist puppet of the divine, but simply the inevitable progress of a well defined and understandable set of physical laws.

In contrast to the physical sciences, mathematics and logic were in no threat of being exhausted. There is no upper limit to the length of a conjecture, so you can always find a new one to prove. But there was a similar optimism in the field. Even if the statements in math are infinite, it was believed that they ultimately encompassed all possible truths. Any truth could be mathematically proven, any falsehood thoroughly contradicted. And the world of math was seen by its practitioners as one of very clearly defined truths and falsehoods. The everyday world is filled with shades of gray, but math is a Platonic, quasi-religious realm of absolutes. It was even believed that you could build a machine that would take in any mathematical statement and print out a proof of that conjecture's truth or falsehood.

Each field of mathematics derives from its own set of base axioms. You cannot do geometry without definitions about points and lines. Integer arithmetic is very different from arithmetic over real numbers. To many, this was an unsatisfactory state of affairs. They believed since there is only one set of all true statements, they should all derive from the same basic facts. Gottlob Frege, a German mathematician tried to unify math, using set theory as a basic set of axioms to derive the other fields of mathematics. Set theory concerns itself with groupings of objects together. The set of even numbers starts 2,4,6.... The set of nations of the world include Germany, Australia, etc. Frege was able to show that with some basic axioms about sets you can derive geometry, arithmetic, etc.

As his second edition of the book was in the final preparatory stages for publishing, Bertrand Russel sent Frege a letter alerting him to the fact that his axioms allowed in paradoxes. Frege had to add an appendix at the last moment, starting "A scientist can hardly meet with anything more undesirable than to have the foundations give way just as the work is finished..." Frege had begun to put math on a highly formalized setting, but in doing so had created a system with infinite valid statements that could not be proven one way or another. Such a mathematical system would not be a Platonic home of all truths, but one filled with uncertainties.

The paradox comes from the fact that sets can contain themselves. "The set of all non-Empty sets" is itself non-empty, and thus contained by itself. In contrast, the set of nations is not a nation, and so is not contained by itself. Does "the set of all sets not containing themselves contain itself?" If it does, then it must have the property of not containing itself, which is a contradiction. But if it doesn't contain itself then it meets the requirements for the set, and therefore does. Whether you put it in the set or leave it out you get a contradiction. There are a number of less mathematical ways to formulate this problem, such as the following: "There's a barber in a town who shaves all men that do not shave themselves. Who shaves the barber?" It seems like a silly game, building nonsense sentences. It seems odd that something as trivial as question about a barber should shock the foundations of the mathematical world. And yet it did...

Russell was purportedly crushed by his paradox. He had grown up with the quasi-religious view of mathematics as a bastion of truth, and hated to now be associated with an attack on that foundation. But as the good mathematician, he could not deny the mathematical truth that set theory did lead to paradoxes. For many years after he left the field of mathematics, unable to come to terms with the damage he had done to the field. Finally he returned, determined to re-establish the foundations of mathematics. With the help of Alfred Whitehead, Russell wrote a three volume book, "Principia Mathematica" designed to retrace Frege's steps while avoiding the paradoxes Russell had discovered. It was an extremely detailed effort. The book contains the famous remark "From this proposition it will follow, when arithmetical addition has been defined, that 1+1=2."...379 pages in. The book is viewed as one of the most important ever written on mathematics, clearly defining the basic logic that validates it as never before. But did he succeed in clearing the paradoxes out of mathematics? In 1931 the extremely eccentric mathematician Kurt Gödel would prove once and for all that anyone setting out on the endeavor of formalizing mathematics in a way that avoids paradoxes was doomed to failure. And with that, what I would view as the modern age of mathematics would begin.

Saturday, January 23, 2010

Could Corporations Use Their New Power For Good?

Corporations now have free reign in running political advertisements. There are interesting questions about person-hood, constitutional rights, and government rolled up into the issue, but at its simplest this gives corporations more control in government. Was that what's been wrong lately? Has the American citizen grown too powerful, and these poor multinational corporations too weak? If only Haliburton and Blackwater had more access to government would we have been able to avoid the corruption of Iraq War contractors?

What bothers me is the idea that corporations could possibly be responsible partners in shaping government policy. Let's pretend some candidate is running for Senate, and promises that if he's elected he'll eliminate the income tax for programmers. That would be a pretty good deal for me. Perhaps the free market would reduce my salary in return, but it'd reduce the competitiveness of outsourcing firms. I'd just about certainly end up ahead. Would I vote for that guy? No. It would be good for me, but I don't believe government is just for maximizing the money flowing into my wallet. I'm better off financially then most people my age, I feel that I should pay my share.

But what if I was CEO of a public software corporation? Could I say "Sure, it'd help me if I didn't have to pay taxes on my programmers, but that's not a good way to run a country. I'm going to speak out against it?" No, I couldn't. I'd be legally barred from spending corporate money in that fashion. The fiduciary duty of an executive means that he needs to put his shareholders interests first. He's legally liable if he doesn't. It's not some liberal distrust of capitalism that makes me think corporations are going to abuse their new found power, they're legally obligated to do so.

The Preamble of the constitution sets out to "..promote the general welfare." A corporation is legally required to promote the welfare of the shareholders over anyone else. There's a fundamental mismatch here. We could outlaw that clause in corporate charters and require them to be good citizens. But I think it's naive to think that would be any good for the economy. Self interest works well in the free market. But the government isn't, and shouldn't be, the market. The distinction between the two has worked out well for the history of democracy, do we really want to get rid of it? In essence, the court decision has given the loudest megaphone to a small group of people, and told them "if you don't use this selfishly we'll take it away." Could that possibly be good for the nation?

Tuesday, January 12, 2010

The Limits of Knowledge, Part I

One of the foundational questions of Computer Science is "what can be computed?" It's a vaguely philosophical question, but it turns out to be approachable from a mathematically rigorous direction as well. I think it's probably the most important thread in modern mathematics (1930's onwards modern...), with interesting implications for the universe and our position there-in (plus the story has a few good characters). And happily, it's one of those mathematical concepts that can be explained without resorting to the use of Greek lettering. It's not the future so much as the recent past, and it's not according to me, just retold, but it's one of those concepts I find interesting enough to want to share with the world again.

So what can be computed? The answer isn't "everything", although that's not immediately obvious. You could build a computer as large as our galaxy, and run it for a trillion years, and there are questions you wouldn't have a definite answer to. Not necessarily even very complex questions. Similiarly, mathematics purports to deal with hard truths and unquestionable proofs, but it turns our not every mathematical question you can think of has an answer you can prove.

But before looking towards the outer reaches, it's useful to look in towards the seeds of mathematics first. A mathematical proof starts with a proposition, then using valid mathematical rules derives that this statement is true or false. The valid mathematical rules are usually just proofs that somebody else already proved true. But those need to follow some set of rules as well. You can build a huge tower of mathematics, but it ultimately needs to rest on something, some ground statement. We call these axioms. Nobody proves axioms. We just say, "yes, that must be true!" and go from there. If A and B are true, then just A is true as well. Why? I don't know. It's what we understand 'and' to mean. It's one of the facts we just start with.

And it's the first limit of our knowledge.

Any mathematical system needs to start with a set of axioms. And because you can't prove these, you don't know for certain they're true. And perhaps more important, you don't know if you missed one. Perhaps there are huge classes of really interesting things you could learn about the universe, if you could just think of this other universal truth.

Or put another way, think of the game children play. "We've got to go." "Why?" "We're late." "Why?" "You took too long getting ready" "Why?" "You were distracted by your toys" "Why?..."

At some point you either need to find your way into a loop, or say "just because". So it is with Math. And so it is with anything. Once we thought the world was made of fire,water,earth and air. Then we broke those down into atoms. Now we think of quarks or strings, but ultimately we're always left with some fundamental bit of reality that's just there. You can reach a bottom, but you've always got to just accept it as true, and accept the fact that their could be another layer you can't see.

Thus as far as physics or religion progress, there's always going to be that nagging question of "is this it? Is there nothing more to reality?" No matter how far our understanding advances, there's always going to be at least one statement we'll just have to take on faith. And if the tower of math and science is on a slightly shaky foundation, the sky above it is just as uncertain. But that's another post...

Thursday, January 7, 2010

Partly Wrong is Wrong

There's an old math game of trying to prove 1=2. As a rule, math games aren't fun. But there's a useful lesson in this one.

a = b
a2 = ab
a2 - b2 = ab-b2
(a-b)(a+b) = b(a-b)
a+b = b
b+b = b
2b = b
2 = 1

Step 5 is dividing each side by (a-b), but it was established that a=b in the first line, so this is a divide by zero, which is not allowed in math. Once you've divided by zero, you can get the numbers to say whatever you want. There are longer examples that try to hide the divide by zero better, but the basic idea in all these is to break a rule discretely.

Card tricks are similiar. Early on you ascertain the identity of the card, by forcing a particular card on the volunteer, or sneaking a peek, or using a plant. Once you know, you can do any audacious thing to seemingly stack the deck against you. The volunteer can shuffle. You can turn your back. Whatever audacious bet you take doesn't matter, because by that point you already know the card.

And if you can do it in math, and in cards, you can do it in conversation. Once you let in a single faulty assumption or implication, you can move very far from the truth. Which isn't to say a single mistake automatically makes you wrong...using divide by zero you generate 1=1 as easily as 1=2. Unlike math, you can also be a little wrong but basically right in an argument. But it's important to remember when evaluating arguments or predictions about the future. A whole long string of reasoning can be airtight, but if there was one hand-waved fact (let's assume X for a second) all the subsequent arguments don't really matter.