2010-02-10

Applied probability and statistics

Speaking of probability and statistics, there is the story of a statistician who told a friend that he never took airplanes: "I have computed the probability that there will be a bomb on the plane,” he explained, "and although this probability is low, it is still too high for my comfort." Two weeks later, the friend met the statistician on a plane. "How come you changed your theory?" he asked. "Oh, I didn't change my theory; it's just that I subsequently computed the probability that there would simultaneously be two bombs on a plane. This probability is low enough for my comfort. So now I simply carry my own bomb."

- Excerpt from Raymond Smullyan, To Mock a Mockingbird and Other Logic Puzzles (1st edition), Knopf, June 1985

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Predictability    Chance

2009-12-08

An unprecedented event

Yesterday, 56 newspapers around the World decided to publish the exact same editorial. They did this to stress the importance of achieving a sustainable result at the United Nation Climate Change Conference in Copenhagen (link) - also called COP15.

The editorial reads:

"Unless we combine to take decisive action, climate change will ravage our planet, and with it our prosperity and security...Climate change has been caused over centuries, has consequences that will endure for all time, and our projects of taming it will be demtermined in the next 14 days."

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Climate Change Conference

2009-12-03

The death of a star

It’s not often you get to experience a star dying. Up until yesterday, I was unaware that I had accidentally collected evidence of this happening. How and what evidence you might ask. Well, this was how it happened.

Primo November I did a minor study where I wanted to correlate the structural elements of web sites with the actual content it provided. I knew this would definitely be possible on the broader level, but I was unsure to what degree this differentiation was possible and what the similarities would look like.

Therefore I began to partition a lot of different web sites into categories. Examples of such categories are portals, blogs, and media. I also choose specialized search engines. Further to this, I knew beforehand that there existed a type of search engine that specialized in finding one thing, and one thing only, namely the infamous torrent files. Torrent files are small files that contain information pointing to the whereabouts of other files. In other words, a torrent file is quite simliar to a telephone book that contains information about the whereabouts of people and businesses. In turn, these search engines knows the whereabouts of lots and lots of phone books, each having information about the whereabouts of a certain number of people and businesses.

To put it simple, choosing this specialization would provide me with a near perfect setup for a comparative analysis.

The dying star I am referring to is the web site Mininova (link). Mininova, whos name literally means little star, is one of these highly specialized search engines I mentioned above. Some weeks prior to November 26th it showed evidence of being a highly used and visited web site. Amongst other things, it showed the top ten most popular torrent searches for each major category. Example of such categories are movies, music, games, and other.

This is the structure of the web site primo November (see picture below). Notice the big flower-like structures emanating outwards from the center. These are the categories I mentioned earlier and testify to its heavy usage.

Figure 1: Structural evidence of a widely used and visited torrent search engine.

So what happened November 26th? Well, according to Mininova, they decided to change their business model on that specific date. And they did.

Actually, it began August 2008 when the Dutch court of Utrecht ruled that Mininova’s business model was illegal according to Dutch law. The changing business model was therefore a response to this court decision and its purpose is to comply with Dutch law while hopefully retaining a revivable business opportunity.

This is what happened to Mininova’s web site within 24 hours after launching their new business model (see picture below). Pretty remarkable isn’t it?

Figure 2: A drastically deteriorated structure that bear witness to a failing business model. (zoomed in)

The structure is heavily deteriorated because the consumers have disappeared to other sustainable search engines. Even Google’s hit counter show clear evidence that Mininova is becoming a virtual black hole. Its Swedish counterpart, The Pirate Bay, who might also face changes to its business model in the near future, is doing more than twice as good. The real winner is surely the other competing search engines, mostly specialized but also generalized, and of course the plaintiff’s new and unique legal position within the Dutch free market.

Ending on this business opportunity note, I strongly recommend that all other business areas take a very hard look at how they can achieve similar unique legal positions before they are overrun by the plaintiff’s unique area of expertise.

Notes

If you're unsure of what the pictures above show, please read my previous blog "Visualizing the web", where I explain the details. (link)

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  World Wide Web    Self-organization

2009-11-24

The butterfly effect anno 1914

Excerpt from Henri Poincaré's Science and Method (1914), where he tries to address the question "How can chance emerge in a deterministic world?"

"A very small cause which escapes our notice determines a considerable effect that we cannot fail to see, and then we say the effect is due to chance.

If we knew exactly the laws of nature and the situation of the universe at the initial moment, we could predict exactly the situation of that same universe at a succeeding moment.

But even if it were the case that the natural laws had no longer any secret for us, we could still only know the initial situation approximately.

If that enabled us to predict the succeeding situation with the same approximation, that is all we require, and we would say that the phenomenon had been predicted.

But it is not always so; it may happen that small differences in the initial conditions produce very great ones in the final phenomena.

A small error in the former will produce an enormous error in the latter. Prediction becomes impossible and we have the fortuitous phenomenon."

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Chaos Theory    The Butterfly Effect    Predictability    Chance    Newtonian Mechanics

2009-11-24

The butterfly effect anno 1390

For Want of a Nail (1390)

For want of a nail, the shoe was lost;
For want of a shoe, the horse was lost;
For want of a horse, the rider was lost;
For want of a rider, the battle was lost;
For want of a battle, the kingdom was lost!
And all for the want of a horseshoe nail.

- John Gower

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Chaos Theory    The Butterfly Effect

2009-11-19

Visualizing the web

I have successfully collected and documented all my contacts and their contacts from LinkedIn in Xml-format. It turns out, at the time of writing, that I have approximately 3,000 1^st and 2^nd degree contacts. I must admit, it was an arduous and sometimes dull undertaking, but it’s behind me now and I can turn my attention towards visualizing these contacts.

And so, I began searching the Internet for suitable source code to derive and build my own graph visualization component. But by virtue of serendipity, I found something remarkable, which made me suspense my LinkedIn project in a heartbeat. I promise to write the LinkedIn blog some other time.

Web pages as graphs

It turns out that the biologist Marcel Salathé, currently associated with the Stanford University, has built a graph component that parses the underlying domain specific language of web pages, html, and visualizes these as colorful minimum spanning trees.

What is interesting with Salathé’s visualization is that it’s so straight forward to pose questions about the structure of web pages and then look for answers. Here’s the color legend he uses to differentiate between the groups of html tags:

Table 1: Color legend used to differentiate tags

Starting with an easy example question to warm up, we could ask; “What does this blog look like?”

Figure 1: http://blog.avegagroup.se/MartinKaarup/

This is the answer; it resembles a nice little “flower bed”. Locating the black node (top right below the little gray flower), we can see it is connected to two gray dots, namely the HEAD and BODY tags. Incidentally, the BODY tag is the one that extends downward, while the HEAD tag extends upward. This is pure accidental, since a graphs main purpose is not to depict topological structures, but only relationships between ‘things’ – in this case, html tags.

Comparing to the actual markup (as seen through a web browser), it turns out that the right side correspond to the static elements of the blog, while the four orange-like wild flowers to the left is the actual blog posts. As expected they consist mainly of typographical and image tags.

Extending the question a bit, we could ask; “What does Avega Group’s blog look like?”

Figure 2: http://blog.avegagroup.se/

This answer is marvelous, I think. We can easily identify the super centralized tree structure, which is so typical for a content driven web site. The number of links is just breathtaking! Emanating from a single DIV tag sits numerous short stories – each demarcated by its own DIV tag and mainly consisting of typographical and image tags. Recall, that the latter is just an extrapolation of what we learned from the first question. As we expect blogs consist mainly of text and pictures. And we also expected that the front page would have more blog entries than each separate blog author’s site. This accounts for superior number of tags found.

Another related question could be “Does other known blog sites share the same overall structure?”. (I’ve picked a blog I frequently read, which explain the restriction “known” in the question.)

Figure 3: http://scienceblogs.com/goodmath/

And the answer is mostly yes. The flower bed that extends towards the bottom right corner is actually a cluster of blog abstracts, which naturally consist of the same typological and image tags we saw earlier. However, we also see two distinctly new structures. Most visibly perhaps is the yellow flower at the left side. We can convince ourselves that this must be the free text search field and drop down menu we can observe when visiting the blog site via a regular web browser. The other prominent structure is bigger and eludes the eyes, if we’re not careful. It’s the hierarchy of link tags that emanates upwards and to the right from the approximate center. This structure, in its semantic presentation, is actually also present in the first figure. In the first figure it was not a mature and hierarchical list of topics, but a more insignificantly small list of topics and therefore more easily overlooked.

Now, let’s turn our attention to comparisons. I have captured a handful of Avega’s distinct blog author’s sites, and presented the result below (I humbly apologize to the absent authors, but there are apparently limits to the quality of service in the application. It flatly refused to produce anything for the absentees’ blog sites):

We can see that there are repetitious structures visible in each tree. That is, of course, the entire surrounding markup that provides the coherent look and feel of Avega’s blog site. And it’s the overall tertiary tree structure itself, which consists of; the aforementioned design template, the menu positioned to the right, and the unique collection of blog entries. In other words, it’s the fork going from the HTML tag towards the approximate center of the tree (the tertiary fork, which sits in the approximate middle in Achouiantz, Granlund, and Ahlbergs tree, but is positioned slightly more right in Hammarberg’s tree. And it’s the menu fork, which is probably easiest identified, by not being the green dot from where a flower bed of predominantly yellow and blue flower emanates – because that’s the unique blog entries.

From these pictures, we can also ask some other fun questions that might or might not have sensible or useful answers:

• Who has seemingly written the most (if we count different tags as containing a nominal length of text)?
• Who has written the smallest blog entry (or guess if the pictures are insufficiently detailed)?
• Who is more consistent with respect to the blog content (size and colorings)?
• Why does Granlund have a big homogeneous gray flower? (see if you can guess what it is by browsing his blog entries)

Another kind of business intelligence

Admittedly, I have examined well over hundred trees; domestic and foreign media outlets, general purpose and specific search engines, various consumer sites along with their nearest competitors, and many others. The reason for this is partly to examine what precisely constitutes the similarities and differences between similar groups of web pages, and partly to understand how such a tool could be utilized commercially to collect business information that otherwise would seem incomprehensible for some people in an organization.

So for instance, we could ask the following question: “How does search engine’s usability for the visual impaired compare?”. For brevity, I have chosen only to examine a single performance metric. In reality, this could be any number of comparable metrics. Further to this, I have chosen to examine search engines and visual impaired people, since they have set of properties that coincide into an easily verifiable test.

The relevant properties are:

• Accessibility. Search engines should be easily accessible to all people regardless of any handicap.
• Markup requirements. Search engines have no valid need of table tags in their markup. Suitable container tags are a better choice – ceteris paribus.

And since we know that improper use of table tags, instead of container tags, is an unnecessary hinder for visual impaired people, we have constructed our own sociological experiment. The only thing we need is to examine a number of search engines for the appearance of red dots.

And here is my result sample:

Yahoo, whose structure actually resembles more that of a portal, than that of a search engine, is the only one that doesn’t use tables. Both AltaVista and Metacrawler rely on numerous tables to hold its respective designs together and we therefore see red dots scattered all around the tree. Google also uses table tags to define its main structure, but has less content and therefore can settle with less table tags. Under these circumstances we conclude that Yahoo performs the best.

It turns out that, whomever I talk to about these trees, each person has a new and interesting utilization. Some talk about fun, scientific, or non-commercial questions. Some think the flowers are look like beautiful artificial art. Others think of how a company could gain a competitive advantage by posing difficult questions. And a nerdy few think of building a web parser that uses a combination of tree structure and knowledge about types of web pages to predict the next html tag, and thereby increase performance. The sheer variety of possibilities, I think, bears witness to Marcel Salathé’s insight into the necessity for visualizing our world in new and exciting ways. He himself is astounded by the number of users that visits his application.

Unfortunately I haven’t got the time to convey all these very interesting ideas and will instead leave you with a smorgasbord of flowers to look at (here) and the Internet address to the application (http://www.aharef.info/static/htmlgraph/).

Have fun!

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Graph Theory    Minimum Spanning Trees    World Wide Web

2009-10-24

Solving the Good Will Hunting problem

I've seen the movie Good Will Hunting from 1997, starring Matt Damon in the role as a mathematical gifted janitor, twice. The first time I hadn’t taken a course in graph theory, the second time I had. Regarding the mathematical aspect of the movie, it makes all the difference. The second time I could actually understand the problem the professor posed when he threw down the gauntlet. In the movie the MIT professor stated a, supposedly, very tough problem that they had worked on intensely for almost two years before they were able to solve it. It reads:

"Draw all the homeomorphically irreducible trees having 10 vertices, such that no vertex has degree 2."

In plain words, connect ten dots together with lines such that all dots are connected to at least one other dot. Further, there must only be one path from any dot to any other dot, which means that circles are not allowed. Lastly, all dots must have 1, 3, or more lines connecting it to other dots, but not 2. Now draw all the different figures that satisfies the requirement.

That's what the gifted janitor did on the white board in the hallway.

Sounds simple? Well, it is – surprisingly simple actually.

In reality, the problem is no harder than any other high school problem. The real problem is quite different, namely that we accepted it was hard because Hollywood said so. A corollary to this claim could be to check the Internet and realize that many people already have solved the problem and some even before the movie. Another corollary could be to spend the next 10 minutes or so to solve it yourself, tell someone you know that has seen the movie, and then watch their reaction.

So, the only thing left now, is to challenge you to solve the problem and to present the solution.

This week I challenged Erik Forsberg, Avega Öresund’s .Net consultant. He solved the problem before he zipped his morning coffee a third time. Can you?

I've hidden the solution from plain view here.

Postad av Martin Kaarup

Kommentarer (1)    Kategorier:  Graph Theory

2009-10-16

My scale-free contacts

One drawback of returning from Avega’s 2009 conference in Karpathos, Greece, is having a head full of ideas and recharged batteries. It manifested itself a couple of days ago. Around bed time, I felt a sudden urge to map all my contacts, and their connections as well, on the professional network site LinkedIn. Supposedly, I should be able to see the scale-free invariance property of a social network.

That night I went to bed at around 4 a.m. and I was still miles from completing my data gathering. I didn’t finish the next night either – or the next. The fourth night it dawned on me. The very raison d’être for my investigation, the scale-free invariance, was the problem.

Since LinkedIn is a typical social network site, it follows the power law function which, simply put, states that the vast majority of people would have few contacts, but also that there exist a small handful of people that would have lots and lots of contacts.

And so, on the fifth evening, I haven’t finished gathering the data yet. I expect to be done in a week or so, and then I can finally begin automate a solution to connect the dots, so to speak. On the positive side, I have finished connecting my 1st degree contacts, and if they are ordered by number of connections, it’s possible to observe the scale-free invariance pattern – albeit with some minor variance, mainly because the sample set is small. It’s truly remarkable.

The center of the universe is… me

References

Postad av Martin Kaarup

Kommentarer (3)    Kategorier:  Graph Theory    Scale-free Networks    Self-organization

2009-09-16

Complexity is risk

Have you noticed how people that are neck deep in complexity almost always ask for a standardized solution? And they supposedly do this to regain oversight.

Which side are you on?

The amazing, almost perplexing thing about complexity and risk is that for over half a century two completely separate communities of practice (at least that’s how we’re trained to perceive them) have a lot in common. Both communities can be found in every “modern” company today and even though they have co-existed for so long, they haven’t shared notes with each other yet! They themselves speak about a huge and famous gap that lies between them and requires extra-ordinary talent to cross (and like most of everything else that’s also attributed famous, it’s most likely because there are massive amounts of money involved).

And what were you taught?

While the curriculum of all renowned business schools naturally includes risk analysis, risk configuration, and risk management, the technologists educations are all almost totally void of such topics.

The future is risky

Steps to better complexity management

Notes

For unknown reasons, people from Denmark have a proverb describing what not to do when faced with too much complexity. Loosely translated it says; “If you're up to your neck in s***, don't hang your head" (From Danish; “Hvis du star i lort til halsen, skal du ikke hænge med hovedet”)

The image is of Thaddeus Beal, an artist resident in USA, and is called Spring Convergence (2005). Thaddeus Beal explores graph theory, complexity theory, and chaos theory to determine the fundamental order in his compositions. Hopefully he doesn’t mind me promoting his artwork.

References (in alphabetical order)

• Kevin Buehler, Andrew Freeman & Ron Hulme, The New Arsenal of Risk Management, Harvard Business Review, September 2008.
• Kevin Buehler, Andrew Freeman & Ron Hulme, Owning the Right Risks, Harvard Business Review, September 2008.
• René M. Stulz, 6 Ways Companies Mismanage Risk, Harvard business Review, March 2009.
• Richard P. Feynman, Robert B. Leighton & Matthew Sands, The Feynman Lectures on Physics, Volume 3: Quantum Mechanics, Addison-Wesley, 1964.
• Yaneer Bar-Yam, Making Things Work: Solving Complex Problems in a Complex World, Knowledge Press, 2005.

Postad av Martin Kaarup

Kommentarer (1)    Kategorier:  Complex Systems Theory    Complexity Theory    Risk Management

2009-09-07

I like ants

Since this is my first blog post I thought it should be memorable and so I will share a secret passion of mine.

I like ants, I really do. Compared to Avega I might even like ants a little bit more. Compared to my wife, well, she’ll always win big, but only because I know my priorities in life – not because of the ants.

Fastest path

Even though I’ve first read about ants five, ten, fifteen years ago, I still enthusiastically teach others about the beautiful fastest path algorithm that ants use to optimize their harvest – and sometimes I also do this against people's will (like when they get stuck with me in front of a white board). I think it’s the emergent behavior that arises from doing simple things tens of thousand times or more that still amazes me.

And so, true to my heart, I will tell you about this beautiful simple algorithm; suppose you have to travel back and forth from A to B, then when you come to a cross road, just be slightly more likely to pick the road that is traveled by most of the people that came before you. That’s it – that’s the essence of the algorithm.

Well, I’ve hidden some minor details, such as how to find out about the people before you. In my human analogy above, we can just add to the requirements that everyone wears the same perfume, which means you can use your nose to decide where the strongest odor is coming from and then go that way – much like how discotheques or school yards function (which in turn could explain why children intuitively understand the phenomena and drunk adults don’t).

Anyway – given enough people, the crowd will eventually diverge onto the fastest path (because people that choose correct will travel the path much faster and in turn leave more odors for the next person to make a slightly easier decision and so on…). In other words, it’s basically a positive feed-back mechanism (and if you're control theory inclined, you can extrapolate its benefits and liabilities).

If you aren’t convinced I’ll bet you the next drink at the discotheque that if you were to spray a woman’s perfume onto one side of the entrance and observed the men’s choice entering (deciding whether to go right or left), you’ll find that more men would autonomously choose to follow the perfume – and vice versa by the way; it’s not the case that men are the only lemmings in this nocturnal game. (And if you’re a child reading this, don’t expect me to let you into any discotheque before you turn 30 or so. And since you’re reading about ants, you’re obviously clever already, so stay home, read some more, get rich, and buy your own discotheque!).

In any case, my only regret is that I haven’t found any justified reasons for using the fastest path algorithm during my programming career and therefore should probably have forgotten about it years ago, but apparently it’s a permanent resident in my long term memory.

Sorting

Well, I wasn’t quite honest. There are several reasons why I don’t forget about ants, namely because they do a whole lot more than just finding the fastest way home from a discotheque. For instance, they can also pile stuff of equal sized objects, which is what they do when moving eggs of different maturity around the nest (and perhaps also when they do midden work outside, I’m not sure…)

I won’t bother you with the details surrounding this algorithm, but only say that it involves moving smaller piles of eggs to the approximate vicinity of nearby equal sized but bigger piles of eggs. The emergent behavior of being sorted arises from doing the task iteratively, starting with a pile of one egg, then a pile of two eggs, then three eggs and so on (much like divide and conquer algorithms such as Quick sort).

In computer science such algorithmic qualities (i.e. being distributed, iterative, map-reducible, and easy to implement) is highly sought after today – for instance, when sorting huge amount of data in a cloud-based mesh of computers (and each computer having multiple cores, just to add some locality to the example).

Recruitment

As I mentioned, there are several reasons why I don’t forget ants and here comes another one; seemingly, a clever recruitment scheme is partly the reason that ants are grand masters at exploiting new unforeseen business opportunities without managerial control. Such agile recruitment techniques should rightly be a study of its own right in every business school in Scandinavia (An MBA in Ants so to speak).

For instance, several R&D intensive trans-Atlantic companies have adopted ant-based recruiting mechanisms to harvest the ideas that flow around the corridors and hallways of their domiciles. These ideas are often cross-departmental and therefore almost always span several communities of practice. Such extreme plasticity surely means that ideas thrown in the air have a greater tendency not to be caught by anyone. And lost ideas might be lost revenue – a quality that investors dislike.

Since the mechanism involves recruitment (which is needed to evolve the sustainable ideas from infancy and into a business case), it requires some notion of agile workforce deployment and might at first scare of smaller companies from adopting such a mechanism. This is a fallacy of thought, in that the natural selection quality of the mechanism also takes care of size differences, release cycles, etc. (much the same way that smaller ant-hills can harvest smaller resource, while big ant-hills can harvest bigger resource – both using the same recruitment scheme).

Resource allocation

Recently, I’ve just finished a book by the biologist Deborah Gordon in which she presents her collected research of the red harvester ant in Arizona, USA. She argues, among other thing, about how ant hills resource allocates their workforce in a distributed manner. Apparently, she has found a single algorithm for all sizes of ant-hills (one size fits all) that can explain how ants allocate their workforce – again without managerial control. One of the algorithm’s most interesting attribute is its use of temporal effects.

Admittedly, I haven’t digested it all yet and can’t really say anything else meaningful about it, other than just point out, that such algorithm would prove interestingly for any industry that are resource planning or logistics intensive (like the shipping industry).

Besides delving into the resource allocation algorithm and hopefully be able to comprehend it in greater depths, I’m already looking forward to next marvelous reason why I like ants.

Footnotes

Firstly, I purposefully used the term fastest path algorithm instead of shortest path algorithm, because while it’s often the case that the shortest path is also the fastest, it’s not necessarily always the case.

Secondly, I don’t know where the pictures originated from, so if they infringe on anybody’s claim of ownership, please let me know and I’ll remove them right away.

Thirdly, my oldest child doens't like ants very much. This summer, at Trollhättan in Sweden, she ignorantly climbed the biggest ant hill she could find and proclaimed to be it's queen. Being pissed on by a million angry ants, literally, cured her dreams of feudal overlordship.

References (in no particular order)

• Deborah M. Gordon, Ants at Work: How An Insect Society Is Organized, W. W. Norton & Company Inc., October 2000.
• Deborah Gordon, Deborah Gordon digs ants, TED Talks 2003, http://www.ted.com/talks/deborah_gordon_digs_ants.html.
• Eric Bonabeau & Christopher Meyer, Swarm Intelligence: A whole New Way to Think About Business, Harvard Business Review, May 2001.
• Eric Bonabeau, Marco Dorigo & Guy Theraulaz, Swarm Intelligence: From Natural to Artificial Systems (Santa Fe Institute Studies on the Sciences of Complexity), OUP USA, October 21 th October 1999.
• Marco Dorigo, Ant Colony Optimization, MIT Press, July 6th 2004.
• David Gordon, Collective Intelligence in Social Insects, http://ai-depot.com/Essay/SocialInsects.html.
• Susan Leigh Star & Geoffrey C. Bowker, Sorting Things Out - Classifications and its consequences, MIT Press, 1999.
• Susan Leigh Star, Got Infrastructure? How Standards, Categories and Other Aspects of Infrastructure Influence Communication, University of California, April 2002.
• Kurt Mehlhorn & Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer-verlag, August 6th 2008.

Postad av Martin Kaarup

Kommentarer (0)    Kategorier:  Inspired by Nature    Complex Systems Theory    Self-organization