Showing posts with label research. Show all posts
Showing posts with label research. Show all posts

Tuesday, December 15, 2009

Algorithm Design

In scientific computing, optimality of algorithms is not always something which receives full consideration by users-- if you want to run a sort or solve some combinatorial problem, you are more concerned with making the algorithm work than looking into how fast it runs. But in dealing with very large data sets, reducing the limiting behavior of your algorithm from N^2 to NlogN can reduce your runtime from something on the order of years to something on the order of seconds. So while there are many computational problems out there for which solutions are known to exist, the practical matter of implementing such solutions is so expensive that they are effectively useless-- but if a new algorithm could be found which would reduce their runtime, we might suddenly be able to use them.

This is the driving motivation behind much of the work that goes into quantum computing. Because bit state in a quantum computer is probabilistic rather than binary, the computer operates in a fundamentally different way, and we can design algorithms which take such differences into account. One vivid example is Grover's Algorithm for searching an unsorted array. Here's a good description from Google labs:
Assume I hide a ball in a cabinet with a million drawers. How many drawers do you have to open to find the ball? Sometimes you may get lucky and find the ball in the first few drawers but at other times you have to inspect almost all of them. So on average it will take you 500,000 peeks to find the ball. Now a quantum computer can perform such a search looking only into 1000 drawers.

So if you were opening one drawer a second, the traditional algorithm would take you an average of six days to run, while the quantum algorithm would take you a little under 17 minutes.

(Now, say each of those million drawers represented a different combination of letters and numbers, and you were trying to find the drawer/combination which corresponded to the password to someone's email account. Encryption standards which would be secure against attacks from a traditional computer are easily bypassed by quantum algorithms.)

While quantum computing still has a ways to go, parallel programming is already providing another alternative to traditional computer architecture. In parallel programming, you split your code up and send it to a number of computers running simultaneously (for our million-drawer problem: say you had 9 other people to help you, you could each search a different set of 100,000 drawers and it would only take 50,000 steps on average for the ball to be found.) So the trick in parallel programming is to figure out the right way to eliminate all the bottlenecks in your code and split up your task across processors as efficiently as possible.

Now, what about a task like image recognition? If you had a couple thousand processors at your disposal and a single image to feed them, what is the most efficient way for your processors to break up that image so that between them they can reconstruct an understanding of what it depicts? You might decide to give each computer a different small piece of the image, and tell it to describe what it sees there-- maybe by indicating the presence or absence of certain shapes within that piece. Then have another round of computers look at the output of this first batch and draw more abstract conclusions-- say computers 3, 19, and 24 all detected their target shape, so that means there's a curve shaped like such-and-such. And continue upwards with more and more tiers representing higher and higher levels of abstraction in analysis, until you reach some level which effectively "knows" what is in the picture. This is how our current understanding of the visual cortex goes-- you have cells with different receptive fields, tuned to different stimulus orientations and movements, which all process the incoming scene in parallel, and in communication with higher-level regions of the brain.

It would be interesting, then, to see what sensory-processing neuroscience and parallel programming could lend one another. Could the architecture of the visual cortex be used to guide design of a parallel architecture for image recognition? Assuming regions like the visual cortex have been evolutionarily optimized, an examination of the parallel architecture of the visual processing system could tell us a lot about how to best organize information flow in parallel computers, and how to format the information which passes between them. Or in the other direction, could design of image-recognition algorithms for massively parallel computers guide experimental analysis of the visual cortex? If we tried to solve for the optimal massively-parallel system for image processing, what computational tasks would the subunits perform, and what would their hierarchy look like-- and could we then look for these computational tasks and overarching structure in the less-understood higher regions of the visual processing stream? It's a bit of a mess because the problem of image processing isn't solved from either end, but that just means each field could benefit from and help guide the efforts of the other.

So! Brains are awesome, and Google should hire neuroscientists. Further reading:

NIPS: Neural Information Processing Systems Foundation
Cosyne: Computational and Systems Neuroscience conference
Introduction to High-Performance Scientific Computing (textbook download)
Message-Passing Interface Standards for Parallel Machines
Google on Machine Learning with Quantum Algorithms
Quantum Adiabatic Algorithms employed by Google
Optimal Coding of Sound

Sunday, October 11, 2009

Steven Strogatz's Sync

Steven Strogatz's wonderful book Sync discusses how synchrony in biological networks is not only common, but neigh-inevitable. His opening discussion of fireflies is particularly vivid: along some riverbanks in Southeast Asia, populations of fireflies stretching for miles will all flash in synchrony, a phenomenon which baffled western explorers for decades. It turns out the effect is easy to replicate in a model-- say you have a collection of periodic oscillators which fire a burst of light at their peak and then reset, you can achieve synchrony if you make it so that each oscillator, when it fires, bumps its neighbors forward a bit in their cycles. Because firing induces a forced reset of the cycle, oscillators will be pushed forward in their cycles until they fall into sync, and then stay locked there; this effect takes off in small groups and quickly grows until the entire network is firing together.

The important points here being that a) neurons do this too (in fact it can be hard to get spiking neural networks to stop doing this) and it's really probably important to coding somehow, and b) you guys, fireflies are totally attempting to form some sort of massive insect-based consciousness here.

You can read more on the subject in the preview of the first chapter and a half, posted on Google Books.

Saturday, July 4, 2009

Spectrogram to Sound

I'm still vaguely searching for a good free spectrogram-to-sound program, but this Sound to Graph to Sound Java applet is a good start.

The default resolution is pretty low, but if you're not interested in any of their demo sounds and just feel like doodling, you can hit the reset button to adjust some of the parameters. You can increase the resolution to MxN = 448x448, and to get the frequency bounds closer to vocal range I'd set FL to 10, keeping FH at 4000 (or possibly changing to 8000). You can also increase the value of NFRAME, which lets you store multiple sounds which you can navigate through with the arrow keys, or check the animate box to play them in sequence.

Mostly so far I have succeeded in making lots of drawings that all sound like frogs. Curious.

Friday, July 3, 2009

23 Questions

Darpa's 23 mathematical challenges in modern scientific efforts, with a distinct emphasis on computational biology.

Larry Abbott's 23 questions in computational neuroscience.

23 is a reference to the father of all such lists, Hilbert's 23 problems posed to the International Congress of Mathematicians in 1900; these problems shaped much of 20th century mathematics, and some remain unresolved to this day.

Monday, April 13, 2009

Supernumerary Phantom Limbs

People with amputated limbs sometimes experience the presence of a phantom limb which continues to exist where their old limb was-- they can perceive pain or temperature changes in the missing limb, and have a sense of its orientation. It seems like this is probably caused by lingering activity in the parts of the brain which previously processed such sensory data coming from the limb.

Well, it turns out that it's also possible to experience a supernumerary phantom limb: for instance, one Swiss woman reported feeling the presence of a pale, translucent third arm following a stroke. Researchers have found that this woman's brain treats the arm just as it would a real one-- when she uses it to perform a task like scratching an itch, an MRI of her brain shows activity in regions corresponding to her sense of touch, as well as activity in the visual cortex from where she perceives the arm's presence. And it relieves the itch where she'd scratched it, too.