Saturday, August 28, 2010

architectural academic crochet

This is one of my recent projects. Just to show that I can crochet something else, not just hyperbolic planes. Since there is a crochet in the title of my blog I should write about it too. Especially because recently one of my friends complained that my blog is too academic, too mathematical, and too serious. I think he meant too boring, just was polite not to say that to me directly. May be he is right, I am too serious. But it is hard not to be serious when you live near the big and serious university and go to the talks that are serious. Just going to these talks mean that you are serious, especially when you go to the symposium early Saturday morning like today.
Yesterday and today there was a symposium Shaping Architects=Shaping Architecture in Cornell.
I am finding it quite fascinating  to listen talks in the areas with which I am not very familiar. Architecture for me associates with buildings - I was fascinated by Newgrange built 5,000 years ago on my trip to Ireland; last week I was equally enjoying walking around San Francisco looking at the different patterns used for exterior decoration of Victorian houses and I was fascinated by modern buildings in Financial District. I have read some history of architecture but it was about different styles, not about how architects get their ideas, how do they think, how do they explore space, and how do they teach their students. This morning I had an opportunity to peak in the kitchen of architects because they were exactly discussing how they teach students design ideas.
Discussion started with an introduction by Prof. Dagmar Richter about the history of teaching architects. First Academies or Schools of Architecture were created in 16th century Florence and France. It was decided then that architects are more noble than craftsmen that were organized by guilds. There is some parallel here with mathematics in Ancient Greece when theory was separated from practice - mathematicians were supposed to think about ideas but calculations had to be left for specially trained slaves. In 16th century architects were supposed to create art for aristocrats. It was defined that architects should stop doing things by their hands but only create ideas. Politically these first architecture schools were against democracy. No wonder they were destroyed during the French Revolution and new type of schools was created - schools that prepared architects for building military objects and state buildings. That has historically created two directions in architecture which are still fighting, and  currently architects are trying to understand where architecture is now.
My particular interest was about the talk by Gisela Baurmann Crocheting Algorithms.
In Gisela's design studio students use crochet as a conceptual model of fabrications and then form there move to digital models. In her talk she was exploring similarities of crochet and patterns in nature on different scales - in visible dimensions and on a cell level:

When only contours are left these patterns from nature become look like a fabric.
When ideas are developed further they start to turn into design.
There are more pictures on her studio blog. Fascinating pictures to foster design ideas can be seen also on Jonas Coersmeir's studio blog.
So - sorry my friend - when I was concentrating on hyperbolic part of my blog title, it was too mathematical=academic. I tried this time to concentrate on crochet part but it turned out also to be academic. Still I hope that not everything academic is boring - at least for me it was fascinating to learn that crochet can be academic....
There are more fascinating projects by Gisela Baurmann and Jonas Coersmeier here.

Friday, August 27, 2010

Lessons from another million dollar prize

 I do remember that on October 2, 2006 Netflix announced a million dollar prize for improving their algorithm used to suggest movies based on the previous rankings by the viewer or mathematically speaking it meant to have Root Mean Squared Error drop by 10% (or Mean Squared Error by 19%).  If nobody comes up with this result, Netflix promised $50,000 for the best result each year. I have to confess that I was hoping that somebody will come up with a better algorithm in a year. But I did not hear anything after a year. Somehow I had missed the news last September about announcing winners of this million dollar prize. So I was really happy to notice in the first seminar bulletin of the new academic year that today Robert Bell from AT&T labs-Research will be talking about this Netflix Prize.

In the beginning there were 50,051 contestants for the prize. It was interesting to learn about the amount of data and parameters of this problem and also that solutions were searched not by individuals but by teams. The whole process was a long and dramatic marathon that ended with a photo finish. First all teams were given training data - it means 100 million ratings over 6 years (2000-2005) by 480,000 users for 17,700 movies (movies here included also TV shows etc.). Then there were test data - last few ratings of each user. Robert Bell gave some interesting details about these ratings - for example, in 2004 people became happier - the movie ratings became higher, why - it is not clear, as he put it - it does not mean that Hollywood became better. Data were scattered - some people rated only movies they liked or did not like, some rated every movie they watched, some rated only occasionally. There were also some extreme cases - one user had rated 17,651 movies (almost every single one) with average rating 1.9 (on a scale form 1 to 5), the other rated 17, 32 with average rating 1.81. One user managed to rate 5000 movies in one day - as Bob Bell commented - that user must have had some computer science background to do so. For unknown reason the most rated movie appeared to be Miss Congeniality. Average number of ratings per user was 208. Huge amount of data, nevertheless 99% of data were missing and certainly not missing at random. Users were identified just by their ID number. It means that if some user did not rate any children's movie, you can assume that this user is not a child. It became clear that what you rate and what don't provides info about your preferences. User behavior may change over the time.
The research team came up with various models - largest one took about a month to create and consisted of billions of parameters.

Statistician G. Box : All models are wrong; some of them are useful.
When solving such large problems it is important to find good teammates. In the process of the competition some teams combined together, some invited helpers. First year Bell's team had 107 sets (methods), at the end the number was over 800. But one of the lessons they learned was that a handful of simple models   achieve 80% of improvement.
The race at the final days of the competition was very very close - when it was 11 days left to go first three teams had results 9.91%; 9.89% and 9.83%. The two leading teams had the same result but the winner was the team who submitted their result 20 minutes earlier...
At the end of course there is a question - how about the money? Robert Bell said that the million dollars initially were important to attract researchers to the problem, later somehow the money issue lost significance. It was the challenge to solve this multi-layered large data problem that kept researchers going. There were interesting ideas appearing during this competition, lots of collaborative work.
Who received million dollars? Well, look here.
More about how this Netflix prize was won.

Wednesday, August 18, 2010

Hope and Disappointment

I was busy - last Thursday I gave a talk in Lion Brand Studio in New York. My friends gently warned me beforehand that I should not take it personally if there will be not so many people because in August everybody leaves New York. I was really surprised that house was full- some people even made it to the talk from Washington DC!
In my stories how my crochet sculptures come along I was telling a story about a dream - in my dream I was crocheting a huge hyperbolic plane, so huge that I could not move my fingers anymore and suddenly it occurred to me that if I could figure out how to do the next move I could solve P versus NP problem. Of course, I woke up before I solved it.... The feeling after was very strange - I never attempted to try anything with this most famous computer science problem. Yes, my graduate work was in Theoretical Computer Science but it was so long ago that seems - it was in my previous life. Then I did not know whether there is any connection between hyperbolic planes and P v.Np problem. This strange dream prompted me to do some research and I learned about Margenstern's and Morita's paper NP problems are tractable in the space of cellular automata in the hyperbolic plane.(Theoretical Computer Science
Volume 259, Issues 1-2, 28 May 2001, Pages 99-128)

They solved the problem on a particular grid that is possible only in hyperbolic plane - it is rectangular grid but made from pentagons. I had to make this grid and this is how this illustration was created:
Very distant touch to the famous problem! I first learned about this problem when I started my work in Theoretical Computer Science. My thesis advisor Prof. Rusins Freivalds proudly showed me a guest book where Juris Hartmanis while visiting University of Latvia had written: " Call me anytime if you solve P versus NP". Of course my question then was - what is this problem?
I already wrote about one of Clay Institute prize problems - Poincare conjucture that was finally announced to be solved. P v NP is another "Million dollar Prize" problem. (The definition of the problem is a question whether P is equal to NP; P being the set of problems that could be solved in a fixed amount of time and NP being the set of problems whose answers could be verified. ) But it is not about who will get million dollars - it is about the understanding why  I was hoping that one day somebody will solve it. It is one of the deepest questions ever asked. I do not want to claim that I can perfectly explain what it is about but here is an explanation: P vs. NP for Dummies. This problem has long history of being a conflict point between mathematicians and computer scientists. Not the only one, have to admit from my experience. I think it comes from different ways of thinking about problems and deciding what is most important.

And now comes an explanation of the title of this blog - Hope and Disappointment - it was last week when headlines in news were saying P vs NP problem solved - but carefully posting a question mark at the end or 

New proof unlocks answer to the P versus NP problem—maybe or Has the Devilish Math Problem “P vs NP” Finally Been Solved?

 Vinay Deolalikar on August 6th announced that he has proved P is not equal NP. If you search Wikipedia for his name you will be redirected to the page about the problem. From a cached copy I learned that
"Vinay Deolalikar was born in New Delhi, India. He completed his masters in electrical engineering at the Indian Institute of Technology Bombay in July 1994, and obtained his Ph.D. from the University of Southern California in May 1999."
It is a challenge now to understand his proof and for him to fix flaws what others are finding in this proof. As Forbes blog say: Now, It's the Slow Roasting of an HP Mathematician

It is not clear is this proof correct or wrong but it is as far as I know the first serious claim of proving this problem. Such problems people attempt quietly - how many others are working on this problem? Nobody eally knows. Will they come out with their ideas now? We will see.

I was following some of these exciting (some icy, some heated) discussions with a delay because I was in New York after a long absence and really enjoyed seeing exhibits in MOMA - Matisse, which is very crowded and no photos, of course. But there is another one - works of Lee Bontecou: All Freedom in Every Sense which I liked very much:

I visited some of my favorite paintings in MoMA, walked in Picasso exhibit - Themes and Variations - it is interesting to see his protraits of wives and lovers which reflect how he was feeling about these women. I wish there would be a drawings next to them by these women how they felt about Picasso - just for the fairness...
When I reached this:
I decided that my understanding of the modern art has ended and I have to move to other place.
There was a great exhibit in Metropolitan museum - I am glad I had a chance to see it - American Woman: Fashioning a National Identity In the morning on NPR I heard Susan Stamberg talking about it and later it was really nice to see it myself. Next to it was another, much quieter exhibit Italian Drawings - I was thinking - I wish I could draw like that... Both of these exhibits were right next to Impressionists - 

Then Turner

And then the painting tyhat really struck me:
It is the painting by Arkhip Kuindzhi - I did not know that his painting was in Met, may be it was on loan when I was there before.

It is worthwhile to get to the Met's roof - of course, the view is great, but right now there is bamboo construction by Doug and Mike Starn.

When in New York I always try to go to some place which I like very much and some place where I have not seen before - it is a reason I love New York - there are always such places! This time I walked on The High Line - it is a city park built 2.33km built on a former freight railroad on Manhattan's West Side between 20th and 14th street

It would be nice after the walk to disappear in Chelsea Market, particularly because it started to rain. Unfortunately, my time was over and I had to catch a bus.

So my hope for the P vs. NP problem is that one day someday will really understand it, may be it will be Daolalikar, my disappointment is about some mathematicians being arrogant and icy about his attempt - may be it is jealousy or may be they are acting like traditional mathematicians usually do...

My hope for New York was, of course, to do more, my disappointment - some people really leave New York in August and I missed meeting them...       Well, there will be other times...