Paul Bohm's Blog

Information Theory: Obstacles To True Artificial Intelligence

enki@bbq.io (Paul Bohm) — Fri, 12 Oct 2012 15:00:00 -0700

With the Singularity Summit coming to San Francisco tomorrow, a lot of people are wondering about how close we are to successfully implementing Artificial Intelligence.

Probably you've seen a graph like the above before. Computers are getting faster. Does this mean we're getting closer to true Artificial Intelligence? Not necessarily.

As I'll show in the following paragraphs, both Artificial Intelligence and the less ambitious Machine Learning (ML) aren't computationally but data bounded. This has profound implications for viable avenues for research and development.

Generally speaking, the goal of AI and ML research is to acquire a digitally executable copy of a model behavior. The specific model behavior desired can range from classifying ("are there humans in the picture?", "ixs this news article about economics?") to predicting values ("how much does a house in this neighborhood sell for?"), to making conversation like a human would ("a chatbot").

Any such observable behavior can be mathematically described as a mapping from a set of finite input sequences to corresponding outputs, or in other words: a function. And any such function can be translated into a corresponding computer program.

That is, we can represent the model we want to learn ("respond to lines of chat messages like a human would" in the chat bot case) as a function, and then in turn said function as a computer program.

The length of the shortest computer program that provides a mapping equivalent to the model function, can be seen as a measure of the complexity of the model. (For example the shortest program that performs addition on input numbers obviously is shorter - that is, has lower complexity - than the shortest program that parses human acoustic speech)

Now, the goal of machine learning techniques often is seen as helping us acquire a computer program equivalent to the model we want to learn. In general, this feat is performed like this: A human writes a machine learning program L, which given training data T, generates desired program M.

The sleight of hand, in case you haven't noticed, is that instead of writing M directly, the human has simply decided to write L which writes M for him. The problem is that if the shortest L is shorter than the shortest M, we're inevitably missing information - there's many many different candidate M we could be writing - but which one specifically are we supposed to write?

We need to acquire this information from somewhere, and the only place other than L we can get this information from is our training data T. T is a list of examples of M in action. This could be a data set of (houses, their location, and their sales price), or a list of pictures and whether they contain a human face, or log files of human chatroom conversation. The problem is that learning from examples without prior knowledge is notoriously difficult - to learn complex concepts we need an impractical amount of examples. (as proven in [1])

So let us recap here for a second: All the information that goes into producing M is a generator/machine learning function L (written by a human), and training data T (acquired through interaction with humans). The information encoded in L combined with the information extracted from T needs to at least match or exceed the information encoded in M. The only reasonable way to extract information from T is to encode information about its underlying pattern in L. That is: All the work needs to be done by humans.

We face the following conundrum: To get a better model, we either need make the learning algorithm more complex/write more code (which is human work), or we need to gather more or better sample data (which requires human work as well). The complexity of the model M that we want to learn can't be essentially reduced - it needs to be captured in a combination of program and training data.

Since these are information theoretical limitations, Moore's law and faster computers do not help. Even a computationally unbounded supercomputer would not be able to break the laws of information theory. Attempts to reduce the necessary work essentially by sophisticated machine learning methods can be compared with attempting to build a perpetuum mobile.

So how do we improve computer models? More often than not the answer is through more and better data. Humans often have knowledge about underlying relationships between data, which helps them write better M and L. But for problems where they themselves haven't understood the underlying relationships, they are no help. Since the contribution of machine learning techniques to knowledge acquisition tends asymptotically to zero from a viewpoint of algorithmic information theory, more or better data is needed.

Interestingly enough economists Mises and Hayek have discovered the necessity of data to decision making already in the 1920s in their treatises on the Economic Calculation Problem. Since markets force humans to interact, they reveal preferences through interaction. When removing the market, this preference data is never revealed. Thus the market is required to acquire the extract the data needed to do economic planning from people's heads. In a similar fashion the problem of AI needs to be approached with additional data.

Either this data is directly extracted from a physical medium we know it to be encoded in (e.g. by scanning our body and brain), or we need to find ways to scale the amount of relevant data available to machine learning systems significantly.

A second way besides scanning would be simulation: If we're fundamentally data limited, and we can't acquire sufficient data from the physical world through adding sensors or collecting data, maybe we can make computers collect data from world's of their own creation. In the simple case this would amount to computers playing games of parametrizable difficulty similar to Chess or Go against each other. It's far easier to specify a game like Go than it is to fully understand it - so in theory we can let the computers explore a search space that provides its own data. The problem is that exploration of such a kind might over time approximate the complexity of a full particle simulation. It's not clear how deep we'd have to search to find the kind of consciousness patterns we're looking for. But we need to keep in mind that we might need to simulate an entire universe to find the patterns we are looking for.

Embodiment is the remaining third way, and one that had been chosen for humanity long before it made its own decisions. Here new bodies come loaded with both sensors and computational power. Since structurally there's no clear boundary between the processes of cognition and living, this could be considered part of an efficient search process for consciousness throughout the entire universe. In this argument, our physical embodiment is actually a fairly efficient vessel, and humanity is more likely than not to become a first super-intelligence. The internet then amounts to said super-intelligence performing brain-surgery on itself, because changing the plumbing makes it capable of acting in a smarter more coordinated fashion, and those of us who develop better information routing technology simply continue the procedure.

In Summary: The real problem of creating good AI is data and complexity, not computational power. The information theoretical bounds described above apply equally to computers of finite and infinite computational power.

In essence, an equivalent question to "can we learn intelligence by observing intelligent behavior" is: Can we learn about the structure of living organisms simply by looking at recorded DNA data. If so, how many DNA samples do we need? A lot. If we could examine the physical organism directly instead, we'd learn a lot faster.

It'll be interesting to see where all this goes.

Post-Script: I've omitted formality in my arguments for the sake of reaching an audience. For a formal argument please see A. Hoffmann, ECAI 1990 and A. Hoffmann, Minds & Machines 2010, whom I've often simply paraphrased and in two cases quoted verbatim.

[1] A Ehrenfeucht, D Haussler, M Kearns… 1989 - A general lower bound on the number of examples needed for learning

Analyzing my Facebook Graph

enki@bbq.io (Paul Bohm) — Wed, 22 Feb 2012 15:00:00 -0800

Tonight I did a manual graph analysis of my Facebook network: Turns out among nodes with a degree of at least 13, there exist three clearly distinct subgraphs. They probably are most appropriately named The Institute, YCombinator and Future Camp.

Centrality ("who is connected to almost everyone else in the subgraph") seems to follow different rules in all three subgraphs. E.g. in the YC graph very successful founders seem to be more connected than less successful founders, and those in turn are generally more connected than employees.

In the two other subgraphs centrality seems to be more socially motivated. Intuitively I feel that it's different rules that govern centrality in The Institute and Future Camp, but I don't understand it well enough to even attempt to put in words. It's clear that seeing only part of the graph (my perspective) adds a lot of noise that makes this data unreliable.

Finally, what I noticed is that I am somewhat fascinated with people who have high in-betweenness. That is, people that are connected to two or more subgraphs that I'm also connected to, but don't necessarily have a high number of total connections. I don't know exactly why, but probably because they are exposed to a wider range of ideas?

In conclusion, exploring this data was fun. I don't think I'm any wiser yet, but I'd certainly like to explore more how centrality and in-betweenness are correlated (first impression: negatively), and if there's anything else I can learn from this.

The Wishes of an Old Man

enki@bbq.io (Paul Bohm) — Tue, 24 Jan 2012 15:00:00 -0800

This was a post I wrote on my 29th birthday

I'd like to thank all of you that have at times walked with me as a friend, besides me as a partner, behind me in support, or in front of me as someone leaving footsteps that I one day hope to fill. Whether now, in the past, or in the future!

I'm tremendously grateful to have met, spent time with, conversed and played with all of you, the amazing people that have inspired me and shaped me in every way, and that despite their usually good judgement of character, have allowed me to call them friends throughout parts of a twenty-nine year long voyage, both back in Europe where I was born, and in my new chosen home near the bay, where i now reside.

I feel, and know, and believe from within the deepest of my heart that that many of you can and will achieve monumental things within your lifetimes. Some of you already have. And I know you will do it again! Keep swimming against the stream, no matter how hard it is at times, and you will achieve the happiness that can grow only from the truth of honest work. Work well done is its own reward, and there is nothing else that comes close.

But let's avoid getting lost, absorbed by the gentle rhythm of our own strokes, while swimming against the stream, pursuing our own goals, oblivious to where we're all going. Let's remind ourselves, and those dear to us, daily that we're all living in pivotal times, where civilization is just at the brink of finally awakening. Amazing times could be ahead. It's so tempting, you want to grasp it. But at this point it could still all go away.

None of us, no matter how important our projects are, can make this future happen alone. Technology is just a tool. Thus let's look around us for means to set others free. Many can't yet fulfill their potential for what amounts to trivial reasons. We're all caught up in our own private pursuits of parts of the puzzle, but on some level, we need to find ways to enable others. Empowering others to empower others can be the most powerful of actions and chain reactions. Give someone a chance and see if you can set them free. And with that I share with you my resolution for the last year of my twenties, and hopefully for years beyond: Take more time to enable others to enable others.

Let me know if I can help you achieve your dreams and set your free, and I'll try my best! Thank you for being my friends!

A 14-year-old could build 1998's Google using her Dad's credit card!

enki@bbq.io (Paul Bohm) — Mon, 16 Jan 2012 15:00:00 -0800

Technology speeds everything up - more so in some areas than in others. While it's easy to see that erecting a 15-story building in two days is faster than it's used to be done, it's harder to get a grip on the giant strides we're making in software construction. Nonetheless, software is probably the discipline with the most reliably accelerating productivity.

Just a few years ago software wasn't moving all that fast. In those days most programming time was spent on squeezing the maximum performance from CPU and memory and programmers like John Carmack achieved lasting fame for their knack for teasing just a little bit more performance out of machines. And a few years before that, as prog21 points out, even writing a working basic spellchecker was a major achievement. You simply didn't have the memory to store a list of words. Never mind building a really good spellchecker, you'd be busy with optimizing the base case.

But whenever hardware advanced, it only took a jiffy till programmers would again use up all that extra power. At that point in time, software's progress was held back by the (comparatively) slow-moving physical nature of hardware. However computer networks were able to free software from the shackles of hardware: If you built your software right, you could just add more servers as you needed them, instead of relying on manufacturers to provide faster and faster hardware.

Google was among the pioneers of networked architecture and built its service using arrays of cheap commodity hardware from the start. But it wasn't until 2006, when Amazon introduced the Elastic Compute Cloud (EC2), that the chains of physicality were finally broken for everyone. Now you could add and remove machines from software as needed. This development opened up a whole new way of thinking about software to every programmer on the planet.

Three years later, in 2009 I proclaimed to a friend:

Today a fourteen year old could build 1998's Google using her dad's credit card!

To put that into perspective, there's three parts in play here: 1998, her dad's credit card, and the software engineering knowledge and tools required to build what Google built in 1998. Let's start with 1998: The internet was much smaller back then. By the end of 1998, Google had an index of about 60 million pages, and Larry Page's web crawler had been exploring the web since 1996. The total amount of data downloaded was probably in the ballpark of 200 gigabytes by the end of 1998. Storing 200GB of data on 33 bleeding edge 6GB hard drives at $370 a piece would have cost about $12,210 non-inflation-corrected at that time. That's without the hardware, electricity, nor bandwidth to actually operate machines to fetch and store the data. In 2009 you'd have gotten a 1000GB drive for $74.99 and could have run it from a single computer, while people regularly download more than 200GB a month on unlimited cable broadband.

So getting the data had become cheap enough for our hypothetical teen's dad's credit card. Crunching the numbers would require a few more resources, but 1998's internet was small enough to be crunched on EC2 with her parents's credit card. Serving the data and answering queries on a popular website without feeling sluggish would also require a few more servers. Let's assume 30 servers would handle the peak load for a start (Altavista was running off 20 multi-processor DEC 64-bit Alpha's in 1998). At not-the-cheapest-at-the-time $70 per server-month on Amazon, that would give us an estimated cost ceiling of $2100/month, with the expected cost being more along the lines of $500-$1000/month. Now I'm sure Dad wouldn't appreciate it, but for many people that's in the ballpark of what they pay for rent and thus affordable.

So theoretically speaking it could have been done in 2009. More than that, price-wise it probably could even have been done in 2006 without ever touching any hardware yourself. But of course money wouldn't have been the only difficulty for a hypothetical fourteen year old trying to build Google in 1998 or even 2009. Just because you can build anything you want in theory, doesn't mean you know how to do so in practice.

But not only has hardware gotten cheaper and easier to handle (through software), but during the same time our collective understanding of best practice software engineering has progressed by leaps and bounds as well. In between 2006 and 2009 many more people became acquainted with highly distributed architectures. More tutorials, libraries, and opensource software were written than ever before. Distributed Databases and NoSQL systems garnered a lot of attention. And with distributed version control systems like Git, code reuse and collaborative development became more commonplace. Many people stopped thinking about how to program individual computers altogether, and started thinking only in networked systems. Because of the wealth of information and code available, and a large community concerned with distributed system problems, a lot of things that were difficult a decade earlier, had become fairly easy to do.

Somewhen towards the end of 2009 I realized that writing Google as it was in 1998 didn't seem as daunting a task anymore. Not only was the hardware cheap, and the information on how to do it widely spread, but a lot of the functionality had already been implemented. Distributed Datastores? Check. Batch Data Processing? Check. Web Crawlers? Check. Web Servers? Check. The age of big data had arrived, because self-taught kids who wanted to could now play with it without asking for permission.

So do I think a fourteen year old could have pulled it off? I sure think so, but I realize in 2009 it would have taken a very tenacious fourteen year old. But that was 2009. If you are skeptic about my predictions for the past, how about applying them to today or 2015? How long till the technology that, at the time, precipitated the fastest wealth generation humanity had ever seen, can be replicated by a teenager with next to no budget during summer break? How long till it's something you write as a pet project while learning to program. Our tools are still getting more powerful, and our collective understanding of software problems is still increasing at a rapid pace. Do you think there's an upper ceiling for how good we can get at writing software? Are we close?

A few years ago, it was hard to find a library providing the functionality you'd need to write your application. A few decades ago the concept of reusable shared libraries had to be invented before you could write one. And if you'd wanted to use a hash table, if you even knew what a hash table was, you'd have to write your own. Today programmers have a wealth of collaboratively developed libraries for almost any purpose at their disposal. When you write software today, you're standing on the shoulders of countless giants.

Personally I believe that a large part of the reason we're collectively getting better at building software is that a portion of software written is software for building better tools for building better tools. We're not even close to peak productivity yet. We're so much drowning in solvable problems, that we don't even know what peak productivity in software engineering would look like.

If you like my writing or have comments, you should follow me on Twitter and Facebook!

Two asynchronous I/O Helpers for Node.js

enki@bbq.io (Paul Bohm) — Fri, 18 Nov 2011 15:00:00 -0800

I've recently started using Node.JS and Erlang. Haven't been this unfaithful to Python since 2001, and of course there are consequences:

IOStream: JS implementation of Tornado's IOStream class for buffered I/O.
Deque: JS implementation of a Double-ended Queue.

Both are MIT licensed. Hope this is of use!

Ephemerisle 2011 Summary

enki@bbq.io (Paul Bohm) — Sat, 18 Jun 2011 15:00:00 -0700

I spent last weekend at Ephemerisle 2011, the third year of the floating festival on the Sacramento River Delta. Lots of people asked me how it was, and the short answer is: awesome - it keeps getting better every year.

The long answer comes with history: I've spent years organizing and thinking about conferences and events and what makes them amazing, back in Europe. When you're regularly taking a few hundred thousand Euros in hand to make a conference, every detail starts to matter to you. How many tracks does the conference have, which speakers do you invite, where do you put the buffet, which rooms do you use for the talks. When I first started DeepSec (disclosure: I'm not longer involved), I spent two months looking at every single hotel in Vienna to find the perfect location.

It's easy to get things wrong too. Most people think conferences are about talks and speakers, but really they are not. It's all about giving the audience the opportunity to connect. Your job as an organizer isn't to connect them, but to remove the obstacles and optimize the connection funnel.

You can imagine that connection funnel as:

Image: What's your events' public image? Which audience does that attract? Who'd come if they could?
Filter: Who really gets there? Many events are too expensive for many that are interested. That filters, but not for awesomeness. Other events have an application process or are invitation only, but that's very prone to missing awesome people who aren't established yet. Some events like Burning Man have natural filters: They filter for dedication and persistence. Being in the desert with only the food and water you bring yourself is a pretty good way to filter for dedication and self-reliance.
Event: Layout of the location and event structure. Once you've got the people there, you still need to give them excuses and opportunities to connect. We all want connection, but we're all a bit shy. Density is an important factor in enabling connection. Have a space with lots of nooks and crannies, and give people a reason to walk through the hallway. Put your conference tracks at opposite ends of the hallway. Have competitions or just events people can observe or participate in. If the location is too big, put up walls to make it smaller and more dense.

If you get all of those right you'll have an amazing event, and your event will have an impact. Not directly, but by connecting people that will go on and work on projects together.

So back to Ephemerisle. What's great about it?

It has an amazing core audience: Since year one, it has had some of the nicest, smartest and most talented people I know in attendance. And every year they bring more of their friends.
It's hard to get there. You first need to hear about it, and then convince someone to host you on their boat. And someone to ferry you to the actual event. There's no central authority who keeps people away, but it's still pretty damn hard to get there.
Once you're there, you have all these amazing people, but it's really dense and intense. There's little space on the water. Only the land you bring yourself, but it's got lots of nooks and crannies. There's a reason all the best conversations at parties happen in the kitchen or pantry. This year we had about 17 boats tied together. On each of these boats a whole bunch of people feel like they are the hosts, and are hospitable and inviting. Also there's lots of activities for people to actually do something useful together and connect. Building a temporary floating city isn't easy, and by contributing you get accepted into the community

So here's why Ephemerisle is amazing. It's got all the important basics right. From here on out, it's just making it better every year. And it seems we're right on track.

Look at some more pictures from Ephemerisle 2011 on Flickr.

Bitcoin's Value is Decentralization

enki@bbq.io (Paul Bohm) — Fri, 17 Jun 2011 15:00:00 -0700

Recently I've read a lot of claims that Bitcoins don't have intrinsic value. I've come to a different conclusion. Bitcoins have intrinsic value if they enable desirable interactions that are not possible without them. Bitcoin is a theoretical and practical breakthrough that makes it possible to decentralize services we couldn't previously decentralize.

To elaborate: Bitcoin isn't just a currency but an elegant universal solution to the Byzantine Generals' Problem[1], one of the core problems of reaching consensus in Distributed Systems. Until recently it was thought to not be practically solvable at all, much less on a global scale. Irrespective of its currency aspects, many experts believe Bitcoin is brilliant in that it technically made possible what was previously thought impossible.

The Byzantine Generals' Problem roughly goes as follows: N Generals have their armies camped outside a city they want to invade. They know their numbers are strong enough that if at least 1/2 of them attack at the same time they'll be victorious. But if they don't coordinate the time of attack, they'll be spread too thin and all die. They also suspect that some of the Generals might be disloyal and send fake messages. Since they can only communicate by messenger, they have no means to verify the authenticity of a message. How can such a large group reach consensus on the time of attack without trust or a central authority, especially when faced with adversaries intent on confusing them?

Bitcoin's solution is this: All of the Generals start working on a mathematical problem that statistically should take 10 minutes to solve if all of them worked on it. Once one of them finds the solution, she broadcasts that solution to all the other Generals. Everyone then proceeds to extending that solution - which again should take another ten minutes. Every General always starts working on extending the longest solution he's seen. After a solution has been extended 12 times, every General can be certain that no attacker controlling less than half the computational resources could have created another chain of similar length. The existence of the 12-block chain is proof that a majority of them has participated in its creation. We call this a proof-of-work scheme.

If that sounds confusing, don't worry. What it means is just that consensus is reached, because computational resources are scarce. You vote with work. To rig the vote an attacker would need to control more computational power than the honest nodes. To ensure it's more expensive for an attacker to purchase the computational power needed to attack the system, Bitcoin adds an incentive scheme. Users who contribute computational power get rewarded for their work. If the value of a Bitcoin rises and thus attacking the system becomes more profitable, it also becomes more profitable for honest users to add computational resources. At any given point, one would expect miners to invest as much resources into mining as is profitable for them. Bitcoin is a currency, because it needs incentives to protect the consensus process from attackers. This computational process ("mining") is not wasteful at all, but an incredibly efficient way to make attacks economically unprofitable. Bitcoin never uses more computational resources than neccessary to protect the integrity of its interactions.

Now let's go back to discussing the value provided by Bitcoin. Essentially it's a means to make consensus in highly distributed large-scale systems, which would otherwise never be able to reach consensus. The value of this is, that it's now possible to build applications in a decentralized fashion, that we previously thought could not be built without a central authority. The most obvious value of Bitcoin is as a medium of exchange for goods and services that can't be easily bought or sold using cash issued by a central authority. But there's more. Bitcoin also makes it possible to fully decentralize the DNS (Domain Name System). In that case, every Bitcoin Domain Name already comes with a cryptographic key pair. That means it also allows us to solve the PKI (Public Key Infrastructure) problem - every name you connect to has an encryption key associated with it that can be verified without trusting a central authority. In case network traffic monitoring prevents people from accessing information either at all or anonymously, Bitcoin makes it feasible to pay for internet relays that anonymize or reroute traffic - that is, it makes it easier to remove central control and fight censorship. The list goes on, I've been hard-pressed to find any decentralization schemes that would not benefit from Bitcoin integration

The pattern here is: Pretty much all of these applications can already be built in centralized form. But often the centralized solution comes with a whole bunch of weaknesses. In the PKI case you'll have to trust over 300 Certificate Authorities every time you make an https:// connection, many of which are located in countries with repressive governments. If any of those 300 entities get compromised or malevolent attackers will be able to read your email, access your bank account, and violate your privacy. DNS is getting censored by governments because they can. And every time you store value in currency, you're trusting a central authority that it isn't mismanaged and thus depreciates in value.

Is there value in Bitcoin? Let me ask a counter question: Is decentralization valuable? If you think that we'll increasingly lose trust in the central authorities that manage the infrastructure we rely on, you might expect Bitcoins to rise a lot in value. If not, that is you believe that authorities will be able to tackle the challenges of the future better in centralized form, then from your perspective Bitcoins don't add value. We'll see.

The Challenge of Recognizing Bold Early-Stage Research

enki@bbq.io (Paul Bohm) — Mon, 11 Apr 2011 15:00:00 -0700

Last Tuesday, Peter Thiel announced Breakout Labs, his newest philantropic endeavour.

Breakout Labs wants to reshape the way early-stage science is funded, and to return scientific innovation to the hands of independent scientists, engineers, and inventors. Funding agreements will typically range from $50,000 to $350,000 but depend on the nature of the project.

Thiel has long been arguing that we're not seeing the rate of progress that we should, and I think he might be right. But what rate of progress are we seeing, and what rate of progress should we be seeing?

Back in 1871, Lord Kelvin observed:

Scientific wealth tends to accumulate according to the law of compound interest. Every addition to knowledge of the properties of matter supplies [the physical scientist] with new instrumental means for discovering and interpreting phenomena of nature, which in their turn afford foundations of fresh generalisations, bringing gains of permanent value into the great storehouse of [natural] philosophy.

If Kelvin's statements sufficiently described the accumulation scientific wealth, we'd expect continuous exponential growth:

Fig.1 Exponential Growth

But progress only seems to follow an exponential pattern on the surface. Not every advance provides the same utility to future research. Progress really is made up from many smaller paradigm shifts, that each create entirely new fields. Initially a new field makes possible a lot of follow-up results, but as it matures, it becomes increasingly harder to make significant discoveries within it. Eventually all the low-hanging fruit have been picked, and revolutionary advances give way to merely incremental improvements. A logistic S-Curve is a decent visualization of this progression:

Fig.2 S-Curve of a new paradigm

Only when we overlay a series of these paradigm shifts, do we move in the direction of exponential growth:

Fig.3 Multiple S-Curves overlayed

Thiel seems to argue that we're not producing these significant breakthroughs at a high enough rate anymore. Through institutionalism, centralization and standardization, we've homogenized the kind of research that can get funding. We've stymied radical experiments in favor of safe, predictable, incremental improvements. To continue making radical discoveries, we need to be willing to accept less centralized control over the direction of research.

True innovation is by definition hard to recognize. Anything that is obvious would already have been discovered. New ideas require rethinking and challenging what we believe to be true and absolute. It's tough for an outsider, and most innovators are outsiders, to garner the level of attention they need to get their ideas accepted. It's only after they've succeeded that we start to idolize their way of thinking, and look towards people that fit the same pattern for the next wave of innovation. But the previous generation of rebels often aren't the ones to recognize the significance of the next. By the very nature of innovation, every new wave will be unlike the previous one. Truly new ideas always look unworkable, boring, crazy, and absurd.

A good example of this we find in the history of game theory: The entire edifice of game theory rests on two theorems: von Neumann’s min-max theorem of 1928 and Nash’s equilibrium theorem of 1950. Like many great scientific ideas, from Newton’s theory of gravitation to Darwin’s theory of natural selection, Nash’s idea seemed initially too simple to be truly interesting, too narrow to be widely applicable, and, later on, so obvious that its discovery by someone was deemed all but inevitable. Today, Nash’s concept of equilibrium from strategic games is one of the basic paradigms in social sciences and biology, and earned Nash a Nobel Prize. Still, the eminent von Neumann initially rejected Nash's ideas, just as Einstein had rejected one of Nash's earlier ideas, albeit more politely.

But Nash was lucky in that he didn't have to ask for permission to conduct his research. Since he was a mathematician and economist with a scholarship, he didn't require funds for experiments. Also Princeton at the time, was a fairly unique institution in that it subjected its students to a maximum of pressure but a wonderful minimum of bureaucracy. The department offered courses, true, but enrollment was a fiction, as were grades. Some professors put down all As, others all Cs, on their grade reports, but both were completely arbitrary. You didn’t have to show up a single time to earn them and students’ transcripts were, more often than not, works of fiction “to satisfy the Philistines.” More than that, not only could he pursue his own studies, but at Princeton he had access to von Neumann and Einstein and many other of the greatest minds of his time. Given that access, he was eventually able to find established mentors that helped him get his research accepted.

In many other sectors however, progress can't happen without initial funding. Also an increasing number of innovators, especially those residing outside of elite academic institutions, lack the level of access to the ears of the great minds in their fields. Worse, as the amount of research grows, and the world is becoming more interconnected, an ever increasing number of researchers and ideas are vying for the attention of a comparatively small count of established individuals that can't thoroughly study even a small fraction of them.

Today, for ideas and proposals to reach high-profile individuals that can support them, they must pass through layers of gatekeepers or committees. But gatekeepers and committees are notoriously bad at recognizing breakout brilliance - they always tend towards the safe average. Thus we're facing a structural problem, wherein the way we discover and promote worthwhile projects can no longer scale with the volume of project proposals produced. If we can't consume the research of our peers anymore, and we're not discovering the occasional brilliance therein, how can that briliance contribute to our own research, and thus fuel progress?

The challenge for Breakout Labs is going to be to find ways to recognize truly exciting projects - not just by being more bold, but by developing new methodologies to determine at scale, which radical ideas are worth funding. I'll argue in a follow-up post, that the most reasonable metric might be a measurement of an individual or team's ability to execute, rather than an assessment of the research idea itself.

( Italiczed parts of this text based on: Nasar, Sylvia (2011). A Beautiful Mind Simon & Schuster. )

Modeling User Information for Food Delivery

enki@bbq.io (Paul Bohm) — Tue, 07 Dec 2010 15:00:00 -0800

A few years ago I helped start what is now probably Austria's largest internet food delivery website. 'Mjam' is an onomatopoeia for the sound you make with your tongue when your mouth is watering in anticipation of something really tasty.

While working on Mjam, one thing we really thought about was ranking quality: How can we learn from our users and find out which restaurants are the best? The better we are at satisfying our customers, the more likely they'd stick around or even get their friends to use our site.

We immediately knew that Pure 1-5 Star ratings wouldn't do. Everyone uses stars differently, and there's interaction-specific attractors to boot (on Netflix people are more likely to rate movies they like, so 5 is more popular than 4, 4 is more popular than 3, ...). The Star rating system also loses a lot of resolution: We don't want to know which 50 restaurants have 5 Stars, we want to know which ones are the best. Ordering restaurants would be a much better fit than discrete rankings.

So we experimented with modeling the knowledge our users had when they made an order: A restaurant was an unknown to a user, unless they had recently placed an order there (within the last two months). If a user knew multiple restaurants, and clearly preferred a few of them over the others, that was a vote. Not ordering from a restaurant you hadn't tried before wasn't a vote against it, nor ordering from a restaurant without knowing any of the alternatives. We completely scrapped explicit votes. Instead we decided to let people vote with their money and real orders. The more a user knew (through previous orders), the more weight we gave to that user's behavior in calculating our rankings.

The method turned out to work out incredibly well: Mjam's ratings are still by far the best I've seen (I'm no longer a shareholder nor do I work with them or have any recent inside information). For newer projects I'm focusing even more on personalizing filters, but I think this kind of information modeling still has a lot of promise for improving a lot of ranking systems. Yelp would be a prime candidate for recommending you alternatives and then tracking over time which one you prefer.

Parex - Parallel Execution for Python and Fabric

enki@bbq.io (Paul Bohm) — Sat, 10 Jul 2010 15:00:00 -0700

I've been planning for a while to release more of the tools I've developed for BBQ. Let's get this started:

Parex is a simple python module that allows you to execute multiple processes in parallel, and then block till they've all finished. I use it with fabric to make deployments significantly faster. Find the code over at github.

Usage Example:

x = TaskManager(cwd=".")
x.execute('ls') # execute commands
x.execute('ps auxw')
pid = x.execute('who') # returns pid
x.wait() # wait till all have finished
for y in x.data.values(): # keyed by pid
    print y.getvalue() # y is StringIO

Follow me on twitter here or sign up for the BBQ betatest.

Logo for BBQ

enki@bbq.io (Paul Bohm) — Sat, 10 Jul 2010 15:00:00 -0700

BBQ, my information filtering project that has made me skip sleep lately, has a new logo and some additional design! I've spent more money on logos than I was planning, but sometimes moving forward is more important than being frugal.

I'll blog more about BBQ shortly, but in the meanwhile sign up for the betatest here.

Multi-Nothing

enki@bbq.io (Paul Bohm) — Sun, 04 Jul 2010 15:00:00 -0700

I used to admire the ability of people to work on many things at once or in succession, but these days I'm much more excited by people who focus intently on just one thing for a long time. It's not the quantity of things you do, but whether the parts work together to create a good whole.

Most Recently Used Wardrobe

enki@bbq.io (Paul Bohm) — Tue, 15 Jun 2010 15:00:00 -0700

Ok, this is probably going to blow you away. After a long hiatus from blogging, I'm sitting at my desk on such a beautiful day and bring to you applied computer science: Behold, the miracle of the Bay Area: The magnificent Most Recently Used Wardrobe.

That is: Hang all your clothes on a bar and whenever you return an item from laundry, append it to the right side of the bar. After a while all the stuff you never wear ends up on the left side - ready for archival or transfer.

Remember: Random Access for pop() but appendright() for Insertion.

The all new paulbohm.com!

enki@bbq.io (Paul Bohm) — Wed, 09 Jun 2010 15:00:00 -0700

It's online and already home to fine interwebs!

PS: This site is running on top of Cassandra/Tornado/Tragedy/EC2.

Update: added some old posts from the archive

Product Discovery not Software Development

enki@bbq.io (Paul Bohm) — Sun, 10 Jan 2010 15:00:00 -0800

If you’re building a new product, your biggest risk isn’t that you won’t be able to reach a mainstream audience, but that you’ll fail to attract even 50 users that love your product.

When embarking on a new venture, your goal isn’t to implement any specific idea in the best way possible, but to iterate as fast as you can, till someone is passionate about whatever product you’ll eventually converge on. Don’t worry about being scalable or cross-platform. So what if IE6 users can’t use your app - you’ve yet to find anyone that wants to use your useless app anyway. Anything that reduces your speed of iteration is poison to your startup at this point.

Yes, we ridicule companies that fail to scale when they start becoming successful, but keep in mind - they’ve become successful and that makes them extraordinary in so many ways. Maybe they didn’t become successful despite being scrappy, but because they were scrappy. Seriously, once you have users that want to use your product but can’t because your tech sucks, you’ve basically won. After all, what you’ve been doing is product discovery, not software development. The tech really is the easy part, since it only becomes important once you have something that people actually want to use.

This article was inspired by a heated discussion on irc.freenode.net #startups about whether not supporting IE and even Firefox is a viable strategy for an early-stage startup. My thoughts are above. I’d love to hear yours. Discuss over at Hacker News.

Florian Hufsky, @oneup, 13.11.1986 - 16.12.2009

enki@bbq.io (Paul Bohm) — Fri, 18 Dec 2009 15:00:00 -0800

Florian Hufsky (“Flo”, “oneup”, “Hufsky”) war mehr als ein geliebter Freund, mehr als ein Pixelkünstler, Hacker und Spieledesigner. Flo war jemand der konstant mit einer Leichtigkeit Ideen, Konzepte, Code und Projekte produzierte, die Ihn nicht bloss nach einem Medium für seine Ideen suchen liess, sondern zum Medium seiner Ideen machte. Jemand der mit 23 bereits eine Partei, mehrere Spiele, Startups, und eine Künstlertruppe gestartet hatte, und jemand der Freunde und Familie hatte die Ihn wirklich liebten. Nicht jemand der etwas sein wollte, sondern jemand der etwas war, und dessen Beiträge und Inspiration noch lange in Design, Produkten und Diskurs weit über dieses kleine Alpenland hinaus widerhallen werden. Und dennoch war er nicht glücklich, fand nicht die Perspektive und Liebe die Ihm gebührte, und sah scheinbar keinen Ausweg. Mir blutet das Herz daran zu denken, dass er etwas übersehen haben könnte - ich wünschte er hätte mehr gereist, hätte mehr gesehen - vielleicht wäre da etwas für Ihn gewesen. Doch unendliche parallele Welten, und wir enden in einer in der ein Freund, ein Vorbild und Inspiration mit so viel Potential, uns bewusst verlässt. Ich kann nicht abschliessen damit, ich spüre nur Wut, Tränen, Verzweiflung. Sein Licht brannte hell, und Ich bin dankbar für die Zeit die er mit uns teilte. Danke Flo!

English

Florian Hufsky (“Flo”, “oneup”, “Hufsky”) was more than a beloved friend, more than a pixel artist, hacker and game designer. Flo was someone who produced ideas, concepts, code and projects with such ease, that he didn’t just look for a medium for his ideas, but he himself became a medium for his ideas. Someone who at 23 years of age had already started a political party, multiple games, startups, and a digital art troupe, and someone who had friends and family that truly loved him. Not someone who wanted to become someone, but someone who was someone, and whose contributions and inspiration will continue to be felt for a long time in designs, products and discourse, far beyond the small alpine country that he was born in. But despite all this, he wasn’t happy, he didn’t find the perspective and love that he deserved, and it seems he saw no way for himself to achieve happiness. My heart is bleeding when i think that he might have missed something - i wish he had travelled more, had seen more - maybe there’d have been something for him out there. But despite the infinite parallel worlds that we live in, we end up in one in which a friend, a role-model and inspiration with so much potential, has left us intentionally. I can’t comprehend, I can’t move on, I only feel anger, tears and despair. His light burned bright, and I’m thankful for the time he shared with us. Thank you, Flo!

Wave, the new X-Windows?

enki@bbq.io (Paul Bohm) — Sun, 09 Aug 2009 15:00:00 -0700

While at the GTUG Campout in Mountain View, Jacob Rus and me turned Google Wave into a collaborative Scientific Computing Environment using scipy.

Working on Wave there and later independently on Operational Transformations (the algorithms behind wave), has led me to conclude that the protocols and ideas behind wave are far more interesting than the promise of the current implementation

Most observers are portraying Google Wave as the future of email or instant messaging, and celebrating or criticizing it as such. In the blog posts I've read, Wave’s merits are analyzed solely based on the current developer UI preview. Calling it a preview is giving it a lot of credit - let's maybe call it a debugger or proof-of-concept instead. Or in other words, people are discussing Wave like it is the newest social networking website, and not an infrastructure protocol under heavy development.

So let’s ignore the high-level “next-gen E-mail” sales pitch for a moment and take a look at the state of Wave today. At its heart is a technology called Operational Transformation (OT). It defines a set of operations, transformations, and the documents they can be applied to.

For Google Wave in particular, the components involved are:

Documents that can be rendered to HTML.
Operations and series of operations that can be applied to documents: For instance, insert a character ‘c’ at position 5, then delete the character at position 9 (Note: this is an example, not how wave's operations really work).
Transformations of Operations: These are rules to change operations, so that if operations are received in different order on multiple clients, the document still eventually converges to the same consistent state.
Robots that can monitor operations and create new operations based
on the operations previously applied to a document.
An early draft of a federation protocol that allows documents to be
hosted on arbitrary servers instead of a central location, for example
at Google.

That's pretty much all there is to it. It essentially defines the data structures of a collaborative document editor, and we don’t really know yet where many of the components attached to them will lead: The federation API is still a moving target, there's no client/server protocol, and robots speak yet a different moving-target protocol. Add a web UI (which right now doesn't even properly speak OT, and is built on an unspecified and GWT-specific protocol) and what you have is a collaborative web document editor with big ambitions. That’s exactly where Wave is right now, and the competition has been here before (maybe without the big vision, but who's to say?).

Now where can we go from here? HTML is a document display system repurposed as an application platform. Wave seems aimed at the same route. So how could that application platform look?

Let me explain using an analogy.

Traditional programs can either directly access input and output devices like keyboards and graphics cards, or they can use the X-Windows protocol, which is more abstract, but has certain advantages. With the X protocol, programs request graphics operations instead of instructing the hardware directly. This level of abstraction enables multiple programs to work on the same screen, cooperate with copy&paste or enhance each other like window managers do.

Programs can even use the X-Protocol over a network, which
means that a program and its server with the screen can run on different
machines. I say in theory, because graphics operations are ill-suited
for high-latency, low-bandwidth environments such as the Internet, and
X-Windows is a particularly chatty protocol. More efficient solutions
like RFB/VNC and NX have been developed, but in general, the pixel transfer paradigm has proven inferior to the high-level web application paradigm that has parts of the UI logic running on the clients in JavaScript.

Now I'm arguing that this new webapp paradigm is still like talking to the graphics hardware directly. Developing custom JavaScript code for changing documents requires re-inventing the collaboration and interoperability wheels over and over again. Wave could be the heart of protocols and standards upon which we can develop the next generation of applications without re-implementing everything over and over again for each new app. Apps would be robots, possibly partially running within the browser, and all I/O would be operations on documents.

This means that every Wave application would be collaborative "for free", and
you could combine multiple apps to interoperate on the same documents, like a latter day OpenDoc. Eventually, documents could be more than just static data, and using the same protocol and algorithms to build, let's say, a collaborative Photoshop in Wave is entirely possible, just like classic web applications have transcended the original scope of HTML.

To give you a little background: I am a software engineer working on distributed systems, and particularly on OT algorithms. I am posting this from the GTUG Campout at the Google Campus in Mountain View where I have just built a few Wave-based apps with my co-conspirator Jacob Rus. Among them is a collaborative scientific computing environment (think Mathematica or Matlab - but based on the awesome Python Scipy environment - screenshot here), and a Wave Robot IDE, which allows you to write wave robots collaboratively from within Wave. Both projects will be opensourced soon. You should follow me here on twitter, if you want to get updates.

Thanks to Christiane Ruetten, Jacob Rus and someone knowledgeable who can't be named for reading drafts of this.

Discussion and comments on news.yc!