Final version of paper

Here's the final version of the paper describing my Master's research at Brown: Lowering: A Static Optimization Technique for Transparent Functional Reactivity. It will be presented at PEPM'07 in January.

The work was very successful: I managed to get a speedup of 7810% for a program that had about 6000 lines of code. The abysmal performance of that program was what motivated the project in the first place.

More...
Rolex Datejust watches: Rolex Day-Date II watch for saleRolex Datejust watchesPiaget...
weddingdressclub: Spring is near,every girl wants to be the bride in the speci...
fanqin: Gucci is famous as top quality, Louis Vuitton Tivoli PM luxu...
adgfh: UGG Fake Women's Highkoo Fake UGG Women's Liberty Fake UGG...
discount shoes: nike shox shoes Womens Shox R4 shox sales online Nike...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: cheap replica watchesCartier replicaConcord watch for saleFr...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
uggboots: ugg boots sale at a time when large heat has set off a winte...

Paper got accepted

I just got notified that the paper describing the work I did for my Masters was accepted to PEPM '07 (Partial Evaluation and Program Manipulation). PEPM is affiliated with POPL, and will be held in Nice, France in mid-January 2007. I'm feeling somewhat mixed about the news, since it's not clear whether I'll get funding to actually attend the conference.

I'm not sure what the rules are with regard to sharing preliminary papers, so I'm not going to link to it until it actually gets published. You'll just have to wait in suspense :)

fasf: Paul Smith has been collaborating with a few different organ...
magicstix: President Inauguration. Sampai Kapan Indonesia Terus Memben...
magicstix: President Inauguration. Sampai Kapan Indonesia Terus Memben...
replica Breitling: replica A.Lange & Sohnereplica BreitlingFerrari replicaC...
weddingdressclub: Spring is near,every girl wants to be the bride in the speci...
adgfh: UGG Fake Women's Highkoo Fake UGG Women's Liberty Fake UGG...
fanqin: Eugenie Wallet Louis Vuitton Eugenie Wallet Loui...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: Christian Louboutincheap Jimmy Choo Handbagsdiscount Christi...
buy cheap puma shoes on puma store: Merry Christmas ! Go to puma store buy a pair of puma sneake...

Learning Natural Language Semantics

I went to an NLP symposium at MIT a couple weeks ago. The most interesting thing I learned there was from a 2005 a paper titled Learning to Map Sentences to Logical Form, by Luke Zettlemoyer and Michael Collins.

I'm pretty familiar with the use of lambda calculus for programming languages, but I'd never before seen it used as a formalism for the semantics of natural language. So the first Amazing Revelation was this:

"What states border Texas?"
λx.state(x) ∧ borders(x,texas)

The second Amazing Revelation was that if you assign "types" to English words, then you can "parse" a sentence directly into a semantic model simply by finding a valid tree of logical deductions. The type system used consists of parts of speech (NP, S, etc) plus a way to represent missing phrases on the right or left. So, for example, you can think of S/NP as being like the function type NP->S, except that it requires the NP to be on the right. S\NP would require the NP to be on the left. Here's the deduction tree for the question "What states border texas?"

But these two ideas are merely the background upon which the paper builds. The real meat of the paper is that if you're given a bunch of sentences and their corresponding LC semantics, then you can automatically learn the initial mappings from words to types. And once you've got that initial step covered, then the rest of the problem reduces to finding the most likely (valid) type judgement for the sentence as a whole.

Pretty damn cool, if you ask me. The paper won the best paper award at UAI 2005, so apparently I'm not the only one who was impressed.

After the symposium everybody went out to dinner at CBC in Kendall Square. I ended up sitting across the table from Luke (the primary author on the paper). He's a really cool guy; smart, calm, and interested in what other people are doing. He's currently studying graphical models (e.g. markov random fields).

All in all, it was a great day.

cheap Yves Saint Laurent: cheap Yves Saint Laurent discount Christian Louboutin di...
Jimmy Choo Handbags on sale: cheap Christian Louboutin cheap Jimmy Choo cheap Yves Sain...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
faff: Paul Smith has been collaborating with a few different organ...
Alain Silberstein replica: cheap replica watchesAlain Silberstein replicaoris watchesom...
weddingdressclub: Spring is near,every girl wants to be the bride in the speci...
adgfh: UGG Fake Women's Highkoo Fake UGG Women's Liberty Fake UGG...
replica Audemars Piguet: Christian Louboutincheap Jimmy Choo Handbagsdiscount Christi...

Graph Theory is Discrete Topology

I just realized that graph theory is basically just a discrete version of topology. Topology is about the connectivity of various continuous spaces. Graphs are about connections between discrete nodes. I know very little about topology, but this suggests some reasons why I might want to learn more about it.

fitch: People all over the world know the abercrombie and fitch,but...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
fadsg: Paul Smith has been collaborating with a few different organ...
Montblanc watch for sale: replica watchesMontblanc watch for saleBell & Ross watch...
adgfh: UGG Fake Women's Highkoo Fake UGG Women's Liberty Fake UGG...
replica Audemars Piguet: cheap Christian Louboutincheap Christian Louboutin sandaldis...
magicstix: MagicStix - MagicStix One Tech Site - Information Technolog...
magicstix: Guam Page. About Guam. Hafa Adai from Guam. Kalakas 671...

Spectral clustering rocks!

In machine learning the other day, we learned about spectral clustering. This has got to be one of the most beautiful algorithms I've seen in months. It doesn't require you to come up with any kind of model for how your data was generated; all you need is a similarity measure between any two data points (e.g. exponential fall off). The measure doesn't have to satisfy the triangle inequality (i.e. it doesn't have to be transitive), but it should be symmetric. Here's how the algorithm works:

More...
Runes of Magic money: You should know Rom Gold, or Runes of Magic Gold if you play...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
indonesia: The Airlines Page. JAL - Japan Airlines. Malaysia Airlines...
indonesia: The Airlines Page. JAL - Japan Airlines. Malaysia Airlines...
uggboots: ugg boots sale at a time when large heat has set off a winte...
cheap ugg boots: women ugg boots women ugg uggs on sale women uggs ...
Indonesia: Indonesia Page | Indonesia | Indonesia Hotels | Indonesia Pi...
cncrouter: laser engraver laser engraving machine laser cutter la...
Kalakas: Guam | Guam Photos | Guam History | Guam Map | Guam Music | ...
Kalakas: Guam | Guam Photos | Guam History | Guam Map | Guam Music | ...

Pictures of dataflow optimization

I've been working on a project to optimize FrTime for the last few months. The idea is to statically analyze a program in order to discover its dataflow dependencies, and then combine lots of little dataflow nodes that don't do much work into a smaller number of big dataflow nodes that do a significant amount of computation. Performance improves pretty much in direct proportion to the fraction of nodes removed, so this can lead to really big improvements.

On Friday I finally generated some graphs to visualize the difference between an optimized program and an unoptimized program. The result is pretty impressive, especially if you like pictures as much as I do. Here's the unoptimized version of a simple program that uses TexPict, an image and text compositing library:

And here's the optimized version:

Red arcs indicate nodes corresponding to conditionals (if statements), and blue nodes indicate data constructors (structs and lists). Black nodes are simple computation, such as addition or subtraction.

Rolex watch for sale: Louis Vuitton watch for sale Maurice Lacroix watch for sale...
Christian Louboutin sandal on sale: cheap Christian Louboutin Pump cheap Christian Louboutin sa...
Jimmy Choo Shoes: cheap Christian Louboutin Boot cheap Christian Louboutin Pu...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
fitch: People all over the world know the abercrombie and fitch,but...
replica rolex: $75 Replica Rolex Watches sale, Our site provides Rolex repl...
jerseysleague: chaoying nfl jerseys Giants Jerseys Patriots Jerseys...
lovebo: China Electronics Wholesale China Phone Cheap Cell Phone...
fasfg: Paul Smith has been collaborating with a few different organ...

Why least-squares makes sense

An offhand comment in my machine learning textbook finally gave me a good intuitive understanding for why you want to square the error terms when doing a best fit of a line to a set of data. Previously, the best explanation I'd ever heard was something like "well. by squaring you guarantee that the total error is non-negative", which wasn't sufficient to explain why x2 is better than, say, x4 or abs(x).

More...
jerseysleague: chaoying nfl jerseys Giants Jerseys Patriots Jerseys...
lovebo: China Electronics Wholesale China Phone Cheap Cell Phone...
fdfe: Paul Smith has been collaborating with a few different organ...
adgfh: UGG Fake Women's Highkoo Fake UGG Women's Liberty Fake UGG...
fanqin: Gucci is famous as top quality, Louis Vuitton Tivoli PM luxu...
Rcat: Respectable Reviews Fat Loss 4 Idiots Review The Tweet Tan...
Hermes Handbags: gucci pink cosmetic case burberry replica handbags valenti...
replica Audemars Piguet: cheap replica watchesCartier replicaConcord watch for saleFr...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
uggboots: ugg boots sale at a time when large heat has set off a winte...

Courses for Fall 2006

I'll be taking Statistical Models in Natural-Language Processing, and Intro to Machine Learning. I'm also planning to audit Domain-Specific Databases and CS Algorithms and Economics.

rolex replica: replica watch replica A.Lange & Sohne replica Alain Silbe...
cheap goods sale.: We are the best online sales for the china wholesale . Here...
Supra Shoes: Supra Shoes Supra Skytop Shoes Supra Society Supra Thunde...
ugg boots: Good day! Thx for your great post and Im thinking about how ...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
fitch: People all over the world know the abercrombie and fitch,but...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: Christian Louboutincheap Jimmy Choo Handbagsdiscount Christi...

iRobot talk at Brown

Today was the first day of Brown's Building Intelligent Robots class, and they devoted the class to an invited talk by someone in the military research department at iRobot. Unfortunately I don't remember the name of the speaker.

More...
Christian Louboutin sandal on sale: discount Christian Louboutin sandal discount Jimmy Choo Han...
Jimmy Choo on sale: Christian Louboutin Boot Christian Louboutin Pump Christia...
fitch: People all over the world know the abercrombie and fitch,but...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
afdasf: Paul Smith has been collaborating with a few different organ...
Rolex Submariner watches: watches replicaRolex Sea-Dweller watch for saleRolex Submari...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: Christian Louboutincheap Jimmy Choo Handbagsdiscount Christi...

Google Techtalks online

I just found out that Google's TechTalks are available online from Google Video. For those missing out on the opportunity to hear smart people talking about intelligent topics (i.e. most people outside academia), you might find it refreshing to watch a few of them.

cheap Yves Saint Laurent: cheap Christian Louboutin cheap Jimmy Choo cheap Yves Sain...
discount Tiffany Silver Jewelry: discount Christian Louboutin Evening discount Christian Lou...
discount Jimmy Choo Shoes: cheap Christian Louboutin sandal cheap Jimmy Choo Handbags ...
Jimmy Choo Handbags on sale: cheap Christian Louboutin cheap Jimmy Choo cheap Yves Sain...
Laptop Battery: Laptop Battery Laptop Battery Laptop Batteries Laptop Batte...
: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
fasf: Paul Smith has been collaborating with a few different organ...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: cheap Christian Louboutincheap Christian Louboutin sandaldis...

Talking with Ken Dill

Yesterday I had the chance to speak with Ken Dill for an hour about protein folding, dynamical simulation of small molecules (e.g. proteins), etc. He was at Brown to give a talk, but I had a class during his talk so I had to miss it. Here's a brief transcript of the ideas I got out of the informal discussion before his talk.

More...
zido: This compilation is really great. Thanks Calgary Web Design...
fanqin: The fashion Louis Vuitton Speedy 25 Bequia Leather bags and ...
ugg boots sale: uggs on sale ugg classic tall...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
nike sports: watches replicaBreguet replicareplica BurberryRolex GMT watc...
replica Audemars Piguet: watches replicaLongines watchesPatek Philippe replicareplica...
uggs on sale: The ugg Bailey Button boots is made with 100% premium twin-f...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
uggboots: ugg boots sale at a time when large heat has set off a winte...
uggboots: ugg boots sale at a time when large heat has set off a winte...

Picture of knapsack problem

In my combinatorial optimization class, we had to write a program to solve the {0,1} knapsack problem, and then characterize its performance. I decided to create a picture of the "hardness landscape" of a particular class of knapsack problem (described below) when tackled via branch-and-bound. I want to share the pictures because I found them fascinating.

Here's a birds-eye view of the hardness landscape, zoomed out 100x, where capacity ranges from 0 to 40,000 and number of items ranges from 0 to 30,000.

Here's a close up view of the upper-right corner of the graph where there seems to be the most "static". Capacity ranges from 39,600 to 40,000 and num items ranges from 2000 to 2300.

Each pixel in these graphs represents the time required to find the optimal solution to the problem at that pixel. Black means the solution was found in zero seconds, while white means the solution took more than 0.5 seconds.

Here's the problem structure I used:

randomItems numItems = map mkItem [1..numItems]
    where mkItem n = Item {weight = (n `div` base) + 1,
                           cost = n `mod` base}
          base = round $ sqrt $ fromIntegral numItems
replica rolex: $75 Replica Rolex Watches sale, Our site provides Rolex repl...
jerseysleague: chaoying nfl jerseys Troy Polamalu Jersey Hines Ward Jerse...
lovebo: China Electronics Wholesale China Phone Cheap Cell Phone...
fadfe: Paul Smith has been collaborating with a few different organ...
weddingdressclub: Spring is near,every girl wants to be the bride in the speci...
fanqin: When a girl has Eugenie Wallet experience the poor day, she ...
Jimmy Choo Handbags: Burberry Handbags| Burberry Handbag| Burberry bags| Burbe...
replica Audemars Piguet: cheap replica watchesCartier replicaConcord watch for saleFr...
ugg wholesale: UGG Bailey Button UGG Classic Argyle Knit UGG Mayfaire ...
uggboots: ugg boots sale at a time when large heat has set off a winte...

My Courses at Brown

Classes started about a week ago. For those who are curious, here are the courses I'm taking:

So far, the first three are really exciting, while the last is a bit slow.

In CS275, we get to pick our own topics, and my first topic is on Software Transactional Memory. I've been interested in STM for a while, and by happy coincidence, the professor for that course, Maurice Herlihy, is one of the biggest contributors to the area. (I'm so bad with names that I didn't even realize this was the case until another student pointed it out to me in the second class.)

CS296-1 is basically formal verification. This week's class included a quick overview of model checking, and last week's homework was to go through the Alloy tutorial. After the model checking class, some of the class hung around afterwards and learned about things like the difference between CTL and LTL, and the mu operator (which was fun because I'd already come across mu in TAPL, for describing fixpoints of infinite types).

In CS258, we're studying approaches for tackling NP hard optimization problems. Today we discussed local search, constraint propagation over a graph, and the simplex algorithm. The current homework is to implement dynamic programming and branch-and-bound implementations of the knapsack problem.

In CS196-1, we're currently doing sequence alignment. But the instructor claims eventually we'll get to things I find more interesting, like protein folding and systems biology.

Also, every thursday there are seminars. Today's seminar was on adding reflection to NuPRL, which was quite interesting.

In short, there's a whole ton of stuff going on, and almost all of it is really interesting.

: rongTiffany Jewelry Online - Discount Tiffany & Co Jewelry O...
DOGTRAINING: belly fat lose weight jobs for 16 year olds jobs for 14 y...
fdfewq: Paul Smith has been collaborating with a few different organ...
Rolex Submariner watch for sale: cheap replica watchesRolex Submariner watch for salereplica ...
Rolex Submariner watch for sale: cheap replica watchesRolex Submariner watch for salereplica ...
http://www.longineswatches.org/Rolex/Sea-Dweller/: replica watchesMaurice Lacroix watch for salereplica Rolex S...
replica Audemars Piguet: cheap Christian LouboutinChristian Louboutin sandal on saleY...
Indonesia: One Simple Tech - Computer News, Reviews and Guides The For...
Indonesia: One Simple Tech - Computer News, Reviews and Guides The For...
Indonesia: One Simple Tech - Computer News, Reviews and Guides The For...