Erlang and Neural Networks Part IV

Ahh, Part IV. It's been long overdue, mostly because I've been changing directions with my startup. I decided to drop everything I was doing, since it wasn't working, and head in another direction with the startup. And lately, I've been messing around with mobile platforms as well as zoomable interfaces. I'll talk more about that another time! But you came for neural networks. Last time in part III, we were able to connect the perceptrons to each other. This time, we're going to look at how you'd actually learn.

The ways of learning

There are many types of neural networks. But this one that we're building is a classic feed-forward neural network. A feed-forward neural network is a linear classifier, and the way it learns is to adjust the hyperplane that separates different classes in multi-dimensional space to minimize classification error, according to what it has seen before. The way that one would adjust the hyperplane is to change the value of the weights in the neural network. But how much to adjust it?

The classic way is to use back propagation, which we'll explore here. People since then have used other methods to calculate the weights, such as genetic algorithms and particle swarm optimization. You can basically use any type of optimization algorithm to adjust the weights.

Carrying the Error Backwards

To figure out the error at the output node is easy. You simply subtract the output from what the output was suppose to be, and that's your error (not exactly, but that's the idea). The problem was, how do you assign weights to the hidden layers when you can't directly see their output? Even if you could, how would you know which way to adjust it, since it would affect other nodes?

The basic idea of back propagation is to get the output of the network and compare its decision with the decision it should have made, and more importantly, how far off it was. That is the error rate of decision. We'll take that error and propagate it backwards towards the input so we will know how to adjust the weights, layer by layer.

I'm not going to go too much into the hows and whys back propagation, since I feel like there's a lot of tutorials out there that do it justice. And I won't go into the proof either. It's mainly just multi-dimensional calculus. It's not too hard to follow, actually. It's really just a matter of keeping the variables straight, since there are so many. I'll skip all that. But I will show and explain the result, since it makes understanding the code a lot easier.

I'm going to assume that most of my audience are programmers that didn't much like math. If they did, they probably wouldn't be reading this, and would have read the proof themselves from a textbook. Therefore, I'll explain some math things that I otherwise would not. Math people, bear with me...or correct me.

Starting from the back of the bus

Calculating the change in weights for the output node isn't too bad. Using my "awesome" GIMP skillz...it looks like this:

We'll start from the back. I color coded it to make it easier to figure out what the equations are saying. (If a variable is bolded, that means it's a vector) The error of output of the training input is:

(1) J(w) = ½ ∑ (t_k - z_k)² = ½ * ||t - z||²

where t is what the output should have been, and z is what we actually got from the neural network. J(w) is basically a sum of all the errors across all output nodes. You'd want a square of the differences because you want to make all differences positive before you sum them, so the errors don't cancel each other out. The double lines stand for norm. You can think of norm as "length of vector". Norm is just a convenient way to write it.

If you wanted to derive back propagation, you'd take the derivative of J(w) with respect to w, and try to minimize J. Remember what I said about going in the direction of steepest change in error? Well, to calculate change, you calculate the derivative (since derivative means change), and that's why you'd do it in the proof. If you want to follow the proof, check out page 290-293 of Pattern Classification by Duda, Hart, and Stork.

The hyperplane

So skipping all the proof, you'd get two equations. One for calculating the adjustment of weights in the output layer (red layer), and the other for calculating the adjustment in weights of all other layers before that (yellow and green layers).

(2) ∆w_kj = ɳ * (t_k - z_k) * f'(net_k) * y_j

This is the equation to adjust the purple weights. It's not too bad, and I'll go through each part.

• ɳ - The eta (funny looking 'n') in the beginning is the learning rate. This is a variable you tweak to adjust how fast the neural network learns. I'll talk more about that some other time, but don't think that you'd want to set this as high as possible.
  
• (t_k - z_k) - Next, note that t_k - z_k aren't bolded, so they are what the output was suppose to be, and the output of the neural network of the kth output node. For us, we only have one output node.
• f'(net_k) - Remember back in part II, where we were talking about the sigmoid function? f'(x) is the derivative of the sigmoid function. If I haven't forgotten my calculus, it should be:
  
  (3) f'(x) = e^-x / (1 + e^-2x)
  
  
• net_k is the dot product of the output node weights with the inputs (y_j) of the output node. Note that y_j is also the outputs of the hidden layer, and it is calculated by f(net_j)--note that this is a regular sigmoid.
  

In equation (2) above, we'll need a part of it to send back to the hidden layers. We'll represent it by a lower case delta (looks like an 'o' with a squiggly on top). It is called the sensitivity. This is what we propagate back to the other layers, and where the technique gets its name.

(4) δ_k = (t_k - z_k) * f'(net_k)

The second equation dictates how to adjust all hidden layers. Note that it uses the sensitivity variable:

(5) ∆w_ji = ɳ * [∑_{k=1 to c} w_kjδ_k] * f'(net_j) * x_i

• As you can see, this is more of the same. The only difference is the second term, which is the dot product of all the output node input weights (w_kj) from a hidden node and the sensitivities (δ_k) across all output nodes the hidden node is connected to.
• net_j is like as before--it's the dot product of the inputs x_i with the inputs weights of the hidden nodes.
  

You'll note that from the perspective a single hidden node, the adjustment of its input weights depends on the set of inputs from the previous layer that is connected to it, and the set of sensitivities and the associated weights of the output layer from the next layer that the hidden node is connected to. net_j is no exception since it is the dot product of x_i and w_ji for all i. You can better see this in a picture. GIMP again.

I know we don't have 3 output nodes and 4 input nodes. It's just to illustrate that from the perspective of the hidden node, this would be the information it needs from the layers surrounding it. In the code base we've written so far, the weights are contained in the node it's connected to. So w_ji would belong to the hidden layer, and w_kj would belong to the output layer. Therefore, the output layer would need to send both the sensitivity and the output layer input weights back to the hidden node.

This perspective is important, because Erlang follows an Actor model, where you model the problem as individual agents that pass messages back and forth to each other. We have now written how each individual node adjusts its weights, and that will help us in our coding.

This also means that as the current implemention is headed, I am assuming an asynchronous model of the neural network. Each perceptron will update when any of its inputs change. That means, like a digital circuit, there will be a minimum time that it takes for the output to reach a correct steady state and for the weight adjustments to propagate back. What this minimum time will be, will probably depend on the number of hidden layers. We'll see if it'll work. I have a hunch it should be ok, as long as the inputs are throttled to wait until the minimal time passes before feeding it a new set of inputs. It might result a lot of unnecessary messages, but if we can get away with it while keeping the code simple, I think it's probably worth it.

Whew. That all took a long time. Probably a good four or five hours. Well, I was hoping to be done by part IV when I started this, but it looks like there'll still probably one or two more installments to this series. Next time, we'll get to the code. I had intended to get to it this installment, but the code will make a lot more sense if you know what the math is saying about it.

In the meantime, I've gotta get to bed. It's like 2am.

Erlang and Neural Networks Part I
Erlang and Neural Networks Part II
Erlang and Neural Networks Part III

Expoential backoff, mofo!

I noticed that facebook doesn't check my blog's RSS feed at a regular interval. I hadn't blogged in a while on my other blog, and facebook stopped checking it. It was only just now that it imported 4 posts at once. It can only mean that they're doing one of two things.

1) They're so overloaded, that they import peoples' blog RSS when they get around to it, and can spare some cycles.

2) They've implemented something like Ethernet's exponential back off when contention happens on the wire.

To me, #2 makes sense. RSS is known for its bandwidth hogging nature, since readers keep pinging the feed. I wrote about adaptive polling before, and it shouldn't be too hard. Based on a recent history of when someone posts on their blog, you can make pretty good predictions as to when they're going to blog next. Therefore, you can check the blog's RSS feed based on that, rather than wasting bandwidth. An easy way is to use a Bayesian classifier to do this.

Nerd time - Issue 6

Hey all,

Hope you had a good July 4th. It's more nerd time--bringing the curiosities of the net at your doorstep. This time is more techcrunchy stuff. So if you read that, you can skip it.

Video's taken off ever since Youtube, facilitated by the ability of flash to play video. Slap Vid is notable because it's the bittorrent of flash video clients. It's a P2P client for video. This is a ycombinator company.
http://www.slapvid.com

The idea to make a clickable world has been around for a while. The idea is to be able to print up URLs as 2D barcodes, so people with camera phones can take a picture of it, and it takes them to the URL. If you're old enough to remember the CueCat, you remember what a spectacular failure that was. But the market was different back then.
http://www.smartpox.com

This is an article on mapping. Google Maps is old news, but the implications of being able to overlay virtual information on top of the real world while you're in it is pretty exciting. The ability to create your own maps has been available for a while now, but discovery of those maps hasn't been easy. And there currently is no mobile earth browser, like there is for the desktop. This in conjunction with the clickable world is worth a thought. Smells like market opportunity to me. Mobile platforms aren't quite mature yet, but they're getting there.
http://www.wired.com/techbiz/it/magazine/15-07/ff_maps

This is a talk on the implications of OpenID. OpenID is a distributed authentication mechanism, aimed to eliminate the need for multiple logins for multiple websites. OpenID in combination with semantic technologies like microformats seems like a neat idea. It's gaining some momentum, as both Sun and AOL have implemented it.
http://video.google.com/videoplay?docid=2288395847791059857

And just for emacs fans:
http://robrohan.com/projects/9ne/
Emacs-like editor on the web!

has_many :jobs, :limit => 4

I saw this ad in my gmail, and found it pretty funny. Swivel is a startup that is trying to be the "YouTube of Data". What they're doing is pretty neat, esp if they can get the correlation of data down. I wasn't aware that they were using Rails, but perhaps they're only using it as a front end, and have some Java backend processing.

While we're at trivialities, you might as well read about "Mel the Programmer." Though Mel's a real person, this is what legends are made of.

More substance next time.

How do you get to work with Richard Feynman?

Long Now: Views: Essays

This is a nice article describing Thinking Machines and Richard Feynman, a physicist that worked on the bomb, and is known for his sense of humor. The article got me thinking...how would I get to work with Richard Feynman? This was what I came up with off the top of my head.

Going to MIT or Caltech would help. Not necessarily those actual places that matters, but being at a place that attracts passionate and smart like-minded individuals would help. That way, you can learn from them and expose yourself to different ideas. I've found that knowing about different far-flung things really help in your creativity and problem solving skills. For example, I never thought reading and learning about the election process was anything other than being a responsible citizen of a Republic. But with the rise of social media news sites, different election systems gives a good perspective on it.

The other point is probably to be working on an interesting problem. Nothing swarms geeks like an interesting problem. I think this is what managers and business fails to take into account. If you're going to get engineers to work on something, you have to cast it as an interesting problem. Don't tell engineers that they're going to work on airline reservation system. Tell them they're going to work on a distributed large-scale scheduling problem. (On the other hand, engineers need to learn to explain to their cocktail party cohorts that they work on airline reservations systems.)

In this day and age of the Internet, the bar is lower than before to get started on working on something important. You can learn all sorts of stuff to get started. But you still need to be in the right environment to help you along.

Thinking in context of what has come before

Startup News:

"This place is a graveyard of hope - everyone here seems to be trying, and everyone seems to be advising - but nobody seems to be succeeding." - Max Klein

I've started to read YCombo news less and less the last couple of months. Most of the articles are about getting funding, a stage which I'm not quite at yet. And I've noticed a lack of concentration on techs and markets at the fringes. To me, that's where opportunities exist, and that's what you have to pay attention to, even if it's 5 years off.

Most everyone seems to think within the context of what was lately successful. "It's a social network that you can post photos and tag them!"

Granted, it's easier to think of things in terms of what has come before, as there's maybe only seven original things under the sun. (I don't know what the seven are, don't ask me). But there are plenty of interesting things going on in research labs, Rubists, Erlangers, and with designers and media communication majors that make the impossible possible.

I think Joe Kraus has it right. He takes things from the land of the nerds and makes them accessible to lesser nerds.

Deploying backgroundrb

Often times you don't get to control what's on the server. Slave or daemon gem required by backgroundrb might not be on your server. To get around that, I froze the gem in the vendors directory. (ie. unpack the gem)

Then in the backgroundrb script under your script directory, add the following right before require 'backgroundrb_server'

# Load gems
if BACKGROUNDRB_STANDALONE == false
  rails_root = BACKGROUNDRB_ROOT
  gem_path = "#{rails_root}/vendor/gems/slave-1.2.1"
  lib_path = "#{gem_path}/lib"
  init_path = File.join(gem_path, "init.rb")
  $LOAD_PATH << lib_path
  
  eval(IO.read(init_path), binding, init_path)
end

It'll shoot up some warning, but you can ignore those, or write your own silent_warnings() method.

BumpTop 3D Desktop can't beat the search box.

This is a video where the desktop metaphor is taken literally for computers. You have move documents around on the desk as if they were real things, using a physics engine. While, neat, I don't think it's entirely the right way to go. This method is only good if you can see a preview of what the document is at a glance. Therefore, for something like photos, it makes sense. But for documents, you often can't distinguish between documents just from a preview. So unless there is also a smooth zoomable interface, I don't think it would be too useful for documents.

The only reason we sort or organize anything on our desk (or otherwise) is so that we can perform search later on. There is no need to sort if there is a default search box as an interface. Therefore, I think what would really be neat is if the documents sort themselves into rankings, or into groups based on what you typed in a floating search text field.

That said, I can see definitely see applications for this technology for augmented reality though. Being bombarded by virtual screens and documents would make anyone feel overwhelmed. Bumptop physics can help lower the information overload for future augmented reality interfaces.

Stringy string string games

I haven't posted in a bit, because I've actually been productive. To lower productivity, I thought I'd post some fun. These are two flash games that have interesting use of spring modeling in the game. One is Double wires(not Double wives), where you can pretend you're someone like spiderman. And A Walk in the Park features an interesting game mechanic, where you play a pooch and you lug around a guy in a wheelchair. You can use him as anchors to catch crackers underneath platforms.

As a result, both have pretty innovative game play. It use to be that if you were below a platform...well, kiss your 1UP goodbye. But not if you have sticky strings or you're leashed to a guy in a wheelchair!

Avatars on the Internet

So this morning, I got an odd IM from a person I didn't know saying to check out his/her WeeMee. It had no link. It might be from a camper I don't remember, or more likely, some guerrilla marketing, and I played into their hand.

Regardless, I checked it out and played their Pogo for Panties! game. WeeMees are basically avatars that people (kids) can create, and attach them to their entire online presence, such as AIM, blogs, myspace, skype. The whole site is a social network, where one can create avatars, and play games on the site. Obviously, I'm not their target demographic, and I won't spend that much time on there.

But I've been noticing a trend with avatar creation, that it's getting easier and easier, and there's certain demographics that are doing it. I've noticed there are avatars makers for Maplestory characters that are popping up on forums, as well as those Voki talking avatars.

For avatars to be worth creating, there has to be a world/context in which it fits that makes it worth showing. In second life or on forums, where interaction with others is the reason why they're there, then yes. Avatar is a form of self-expression that others you're interacting with will respond to. On blogs, not so much, since it's what you write not what you look like, that are important on blogs. Same with wikis.

Perhaps there will be a new form of the web that allows avatars to run about in a 'room' where they can do things together, like play soccer or tag, or draw collaborative pieces. And to go from room to room, you simply go from page to page. In a web like that, there will be room for avatars.

"MySQL server has gone away" on textdrive

Debugging is always hard, because you have to understand what's going on. In this day and age of leaky abstractions, there's just always more and more to know. This is why I think concepts are important. If you know concepts, you can more readily figure out details.

So I had a quizzing error last weekend that I was scratching my head over for about two days. This was mainly because I was getting the errors from backgroundrb. It would just hang with no exceptions reported. As it turns out, there's a bug in Backgroundrb 0.2.1, the latest version.

Thanks to Mathais on the Backgroundrb mailing list, my problem was exactly as he describes. I monkey patched it and the backgroundrb server log started spewing errors out. It was about MySQL servers going away.

After reading about why MySQL goes away at all, I figured out that one needs to check MySQL's interactive_timeout setting. The database will drop the connection to it from the client (in this case, the web app), if there has been no activity for at least that amount of time. By default, it is set to four hours. On the server I put the app on, however, it is set to 10 minutes.

There were a couple solutions to this. One could be, as I posted before, to retry the connection. The other is a setting that I found in Rails.

ActiveRecord::Base.verification_timeout = 570

I put this in the environment.rb file under config to keep the connection to the database alive. I set the timeout to be under the interactive_timeout, so that Rails will keep telling the MySQL server that it's still around.

I don't know if this is exactly a good idea, since on a shared server, that means everyone will be holding on to connections they're not using. I'm not sure what the performance implications are for a long standing connection is, if there is any. But for now, it seems like it's working.

TED | Talks | Jeff Bezos: After the gold rush, there's innovation ahead (video)

TED | Talks | Jeff Bezos: After the gold rush, there's innovation ahead (video)

Jeff Bezos, the guy that came up with Amazon, is probably on spot with how it's the beginning of the innovation on the Internet. But if history is any indication, people that come after this won't be remembered until a new paradigm or market is built on top of the Internet.

I can't exactly imagine what's possible with the rising technologies. Human-centered interfaces (or the complete disappearance of interfaces), tools that predict your behavior using AI techniques, an emerging theory of the brain, nanotechnology for intelligent materials, materials that change shape, programming genetic materials of living cells, personal fabrication, wireless power, open source hardware, social management agents, and instant information anywhere in the world at any time.

Sometimes, when I look at what I'm working on, it gets me a little depressed to see how rudimentary (by today's standards) is. But I get excited when I see where it is going, and how it carries the future with it.

Using ensure in yielding methods

I never really ever find too many occasion to use 'ensure'. It's a Ruby keyword that you can use for blocks of code that ensures, no matter what happens, exceptions or not, the code will be run when the block is finished. And then a quickie that I found in the rails core:

  def silence_warnings
    old_verbose, $VERBOSE = $VERBOSE, nil
    yield
  ensure
    $VERBOSE = old_verbose
  end

It does something simple, just silences the warnings for a particular block of code. On first glance, I would have just written it without the 'ensure'. However, that won't work for yielded blocks that call return or if exceptions are thrown in it, I think. This way, no matter what happens in the block, it will always restore the state that it changed.

Avoiding the SUDO police with Capistrano

When deploying on a shared host, often times, you won't be able to sudo anything. I was originally thinking that I had to override the cleanup task in cappy, but a quick look in google found: Avoiding the SUDO police with Capistrano. You can simply "set :use_sudo, false" in your deploy.rb. Tip!

Surface computing and building your own hardware

Microsoft Announces Surface Computer

Microsoft recently announced their surface computing platform. It's where you get to manipulate objects with your hand on a screen. I think after Minority Report, everyone wanted something where you could manipulate virtual objects. Since there, there's been a realization of that. But few of us had the imagination/drive/ability to actually do something about it.

I had seen simple demonstrations of this type of interface at malls, where a projector and a camera would use occlusion to calculate interactions with the objects. But it was kinda like having a stub to manipulate objects--you couldn't pick them up and manipulate it. Microsoft's surface computer seems to have done away with that, and added a sense of interaction between real objects and the virtual ones in the surface of the desktop--so one can load photos, simply by dragging the photo 'into' the camera.

As for multitouch sensing aspect of surface computing, it's not the first. The idea has been around since the 80's, if not earlier. However, the first demonstration that permeated the web was Jeff Han's demo at TED. Multitouch-sensors weren't available commerically, so you'd have to be able to build your own. According to Jeff in the talk, he said it was low cost and scalable. It makes me suspect that many EEs could have built it. But we didn't.

"People that love software want to build their own hardware." - Alan Kay

I use to think that this quote was only applicable in the days when software was much closer in abstraction to hardware; when people were writing in assembler and C. Nowadays, the only people that seem to do that are embedded programmers, and having done embedded programming for sensor networks, I can say it's not half as fun as web or application programming. Having to manage memory, or build your own malloc wasn't fun, to say the least. It was kinda having to time the spark plugs in your engine to go, instead of just pushing on the gas pedal.

However, I've taken a new view to the quote. When I think about all software, they all process information in some way. The input has to come from somewhere, and the output has to go somewhere to realize the bits in some form. However, the inputs are limited by what humans are willing to enter, and more importantly in this post, what kinds of hardware that will collect this data.

I can't wait until clothes keep track of themselves and match themselves. Technically, it's possible now to write the software, but one would have to enter the information by hand so that the computer can do the tracking and matching. But if there was hardware for clothes to serve this information, then it expands the space of information for software to operate on.

In this light, I can see where the quote is applicable. To expand the reach of software to access information that is only currently available in the physical world, you'll have to be willing to build hardware.

Capistrano tasks for BackgrounDRb — Bryan’s Bytes

Capistrano tasks for BackgrounDRb — Bryan’s Bytes

Here's a good little snippet I found for running BackgroundRb through Capistrano. Not much commentary from me, other than hurray~ I had wondered about why it wasn't working. I didn't know nohup existed as a command--I've always used the trailing '&'. Goes to show you that a little background goes a long way.

Twittering as a platform

Amazon is posting their deals on twitter. I'm not quite sure that people would want deal ads on their cell phones all the time...

I'm kind of amazed, as are other people in the naysayer category have been, that Twitter had taken off as it has. At its basic form, it's just passing back and forth messages, a problem seemingly solved by email decades ago. However, twitter obvious is not a question of the underlying technology, but rather, how it is presented to and used by people. It's gotten people use to the idea of instant self-expression, no matter how inane--for better or worse. I would have chalked it up for sensors to monitor and log ourselves, but twitter demonstrated that people will report or say anything if there's an audience. Perhaps trolls have already paved the way in this regard.

That said, I think it's easy to write Twitter off as a fad, since the world's largest collection of quips doesn't quite seem to make the world a better place. My guess is that there's probably value in Twitter, but only when it's married with other sorts of data or text processing. Just off the top of my head, geospatial data and emotion detection algorithm on twitter data could generate a heat map of how people are feeling place to place, or time to time. I imagine advertisers would find this information valuable, since they can set up targeted advertising when people are statistically most vulnerable to impulse buying at a certain time or place.

If twitter can manage an API or platform to support this sort of thing, they'll be around for a while, I think. If not, well, at least we'd have the largest collection of quips for the archaeologists of the 22nd century.

Photosynth: stitching photos in 3D

Photosynth presentation | Venture Itch

I think this is a bit of old news, since I wasn't running windows XP in order to view the demo at their website. For the last 10 years or so, I've always thought that computer vision has been still trapped in the realm of research labs. But things are starting to bear fruit. Image registration (lining up images) isn't an easy task, since lighting, shape, perspective all have to be taken into account. It becomes especially from difficult if you have to do it from 3 space, as is done in the demo. However, it seems like everything's preprocessed, so it looks fast.

I don't think it's a far stretch to say that you can also register people's faces, so you can find all the images with your face in it, taken from different perspectives.

I also wouldn't be surprised that all the tagging of people going on in facebook photos is training a classifier to recognize and register people's faces.

The ones that push innovation and create new markets are the ones that open up possibilities, and show others what was previously thought impossible.

COMET meets mod_mailbox

COMET meets mod_mailbox is an interesting (new to me, anyway) way to think about asynchronous push of data from server to client. I have tried my hand at using periodic calls from the client javascript to the server for information, and it's a load on the server, even when there's nothing going on. And it certainly doesn't make it seem as responsive for chat-like web applications.

Many people have done it before, it's an old technique. I've seen in in the Dojo toolkit, as well as some others...but I still haven't really seen a nice standalone solution that you can plug in. Ie. I haven't gotten off my butt to write it in javascript so that it can be nicely package...hoping someone else will.

The 3 body problem in Erlang

The three body problem is a simulation of the paths objects with mass in space would take, if all three had gravity effects on each other. With two bodies, the problem can be solved analytically, as done by Kepler. But with three bodies, the paths are chaotic. If you just hit play on the last link, and watch for a minute, you'll see what I mean. And that's the easy version of the problem, since the two suns are fixed. If they were three bodies of comparable masses, then it'd be even harder.

From Ezra: http://ezrakilty.net/research/2006/02/3body_problem_in_erlang.html

The first conceptual problem I hit was the question of synchronization. In order for the sim to be a decent finite approximation to the continuous world of physics, we need to break it into discrete time steps, each of which depends on the previous time step (at least, that's the only way I know of to get a fair approximation). This means that each particle can't just crunch away at it's own speed, working as fast as it can to calculate its position at various times. Easily the particles could grow out of sync with one another, making an inaccurate physical model.

I hadn't thought about this, but I think Ezra is right. In terms of simulation of the 3 body problem, if the correct calculation in the future depends on current calculations, and the current calculations depend on each other, you need to make sure that the calculations are 'in step'.

This calls into question my thought before that asynchronous simulations would work, since whenever the messages arrive, that's when they arrive and process them. In a decentralized simulation of termites gathering wood chips, I imagine an asynchronous simulation would suffice. It doesn't really matter what exact paths the termites take, but rather, the end result of that chaos. But in a gravity simulation, asynchronous simulation doesn't seem to work, because what you're interested in is the actual paths.

If the calculations of all other threads must be synchronous or in lockstep, it would seem like it would give an upper bound to how fast the simulation can go, even in a multi-threaded environment. Since the calculations will be wrong, the further into the future you calculate with slightly incorrect values, what kind of useful computations can you do if you don't have all the initial conditions in your formula?

The only thing I can think of is if you had different sets of three threads--one for each mass--processing the simulation at different simulation times, you can reduce the processing load for the trailing set of threads. So say you had a leading set of threads that operated on simulation time of t + n always. That leading set can narrow the scope of possible answers. Since it knows it's operating on a chaotic system, it knows that what the error is given a certain lead time of n. Therefore, it should be able to limit the upper and lower bound of the possible right answers. Then, the trailing set of threads that operate on simulation time of t, only has to adjust the error, which hopefully is less computationally intensive.

Google Gears Lets Developers Take Apps Offline

Google Gears Lets Developers Take Apps Offline

This is certainly newsworthy. Google announced Gears, which is something that you install on your desktop to be able to operate online applications offline. I remember about 3 to 5 years ago when Google said, no, we're not interested in desktop, because it's not what we're good at. We're doing search.

If anything I think they learned from Netscape's mistake in the past. Marc Andersen, the founder of Netscape, announced that, as a startup, they were taking on Microsoft, and was going to beat it to the ground. Of course, when you use strong words like that, you're going to get Bill Gate's attention, and it's always dangerous to wake a sleeping dragon, when you're not bigger yourself.

Despite the ever growing ubiquity of wireless connections and connectivity all around, I think there's still a place for offline applications. This sort of thing to me, isn't really about being able to do your work on planes, though it's certainly useful for that. To me, this is about caching results that the user might possibly want to see/do next, so that the user experience is fast and responsive without possible network latency. While AJAX is fast, and tolerable for most things, I imagine that there will be some applications that can make good use of this type of offline caching mechanism, so that what was impossible before is now possible.

Of course, caching is irrelevant when the bandwidth is high, but you will either find yourself 1) in places where bandwidth is lower or 2) the bandwidth requirement for your dataset is higher than what you currently have. Mapping applications come to mind as benefiting a lot from caching mechanisms. And if bandwidth jumps up, that makes caching in mapping applications obsolete, there will be other datasets that will be too large to stream in the future. I can only imagine classifiers or their training data sets being one example, as well as a record of the user's digital life.

Update: I didn't mention this, but I think it makes even more sense for mobile devices, per this opengardens post on it.

Internet retailer connects with TextPayMe - Puget Sound Business Journal (Seattle):

Internet retailer connects with TextPayMe - Puget Sound Business Journal (Seattle):

This is a bit of interesting news to me. Originally, I was wondering where textpayme was going to get its traction. Amazon apparently is the answer. While mobile payments is an idea that's not new, and is currently implemented in Japan and other Asian countries, it still doesn't have much traction in the states.

I'm a bit amazed at what's possible through the limited common cell phone interface. Mobile phones are gaining in power, and lots of people anticipate that something's around the corner, but no one knows on which platform, and what's going to be built on top of it. Others are more dismissive, saying that mobile phones are underpowered devices that have limited interface, and therefore not exciting to develop on, compared to the web and desktop.

I think they forget that many said the same about web applications when they first started in the 90's. Web applications back then were clunky at best, and didn't boast a responsiveness until two years ago, when google maps came out.

In addition, mobile devices aren't just small desktops. They have characteristics that are unique to the platform. They are always on, considered personal devices, always on a person, always connected, has sensors on it, and knows its location. While mobile video and music currently offered by the carriers is nice, I don't think it quite hits the spot yet. The mobile application that plays to the platform's strengths will be the one that hits it.

Google maps street view released~

2140 Taylor St, San Francisco, CA 94133 - Google Maps

Google just released street views in SF. You can see the street corners of the city as if you were actually there. That's kinda amazing. At this point, they have enough man power to go and scour a city I suppose...or they bought this information from another company (or the whole company itself) that was doing this. I like how the street arrows tell you which way is north when you're panning around.

I think the potential for this is in augmented reality for mobile devices. I would not be surprised if Google either released a mobile phone or a mobile phone application that allowed you to do the panning in real-time, all the while telling you which way is north, as well as where the nearest gas-station/food/store is.

What I think they'll miss is the potential for social information such as, where your friends are all gathering. I'd chalk it up to Loopt or Facebook to see the potential for that.

Upgrading backgroundrb

When upgrading to backgroundrb 0.2.x, make sure you delete the old ./script/backgroundrb directory. Also make sure that backgroundrb.yml is renamed/deleted. After installing, run "rake backgroundrb:setup" to generate the appropriate setup files.

If you get something like
"LoadError: no such file to load -- slave"

Make sure you have the gems, slave 1.1.0+ and daemon 1.0.2+ installed.

Then, according to the mailing list, if you get:
"ERROR: there is already one or more instance(s) of the program running"

Make sure you delete the old log/backgroundrb.pid . Thing should work after this.

Exploring: reCAPTCHA: A new way to fight spam

Exploring: reCAPTCHA: A new way to fight spam

This particular piece of news has been floating around lately. It's a CAPTCHA service that also uses the CAPTCHA information entered by users to teach computers how to digitize books.

It's so freakin' obvious, I slapped myself on the forehead. I even advocated and watched Luis Von Ahn's videos on human computation, and didn't think about it. Anyway, it seems a little bit odd, though, using a technique that computers can't solve to teach computers how to read--hence solve CAPTCHAs. Not knowing enough details--I wonder if the success of reCAPTCHA will call for the demise of the CAPTCHA.

The usual concerns of cheating were rampant on reddit comments. "What if people just put in random stuff? Then you'll have a computer that spew out crap when digitizing books." If his lecture on the ESP game was any indication, he has a number of ways to fight it (not to mention he specializes in online cheating also). In the ESP game, he counteracts cheating by giving the player a couple ones he knows the answers to and sees how much they're off. Also, he keeps track of the statistics for each image as well as throwing away results randomly. It's a little hard to see how he'll track individual users--other than through their IP--but otherwise, one can feasibly use the same methods for reCAPTCHA.

Naive Bayesian Classifier Hashed and Slashed

I know, I've been bad at posting over the course of the week, where readers would be more likely to be reading this stuff at work. But I have been busy myself too...mostly thinking about non-technical stuff.

Well, some weeks ago, I spent some time looking at Bayseian Probabilities. I learned it way back in high school, though I never gave it much thought. Then I stumbled on it again in college in my ECE courses, and nearly failed the class. And then I took it again in grad school, and though I did well enough in the class, I still felt weak in probability.

This time, when implementing a bayesian classfifier, I learned in and outs of a seemingly simple naive bayesian classifier, and I learned how to spell 'bayesian'. That 'e' after the 'y' gets me every time.

Anyway, I was looking at Paul Graham's famous a plan for spam, and I couldn't figure out where he got that last formula. Kinda mad at myself for not seeing it earlier, cuz, it really is pretty simple. Anyway, it took me a while, but I worked it out. Turns out I learned more when I implemented it...or rather, I would have learned it had I concentrated the first two times.

We know Bayes Theorem is as follows:

(1) P(a,b) = P(a|b) * P(b) = P(b|a) * P(a)

With some algebra of the above we can also derive

(2) P(a|b) = P(b|a) * P(a) / P(b)

But also note that if we take (1), and put a given 'd' behind it, it'd hold true if the probabily on the other side also had a given 'd' behind it. If you draw out the Venn Diagrams, you'll see this is true.

(3) P(a,b|d) = P(a|b,d) * P(b|d) = P(b|a,d) * P(a|d)

We also have the Total Probability Rule, which says that the total probability is made up of its parts. If you apply bayes rule, in (1), you'll see that it's true.

(4) P(b) = P(b|a) * P(a) + P(b|a') * P(a')

So this means that Baye's rule in (2) can be rewritten with (4) as:

(5) P(a|b) = P(b|a) * P(a) / (P(b|a) * P(a) + P(b|a') * P(a'))

We also need the Probability Chain Rule. It says that the joint probability of a, b, and c can be rewritten as the following due to equation (1), applied over and over again:

(6) P(a,b,c) = P(a,b|c) * P(c) = P(a|b) * P(b|c) * P(c)

And lastly, the Independence Rule, which makes the bayesian classifier naive:

(7) P(a,b) = P(a|b) * P(b) => P(a) * P(b) iff "a" indp. from "b"

Now, we can solve for what's the probability of spam given these joint probability of words, where each word is considered an orthogonal and independent dimension?

P(s|f0, f1) = P(f0, f1|s) * P(s) / 
(1)                P(f0, f1)
            = P(f0, f1|s) * P(s) / 
(4)           (P(f0, f1|s) * P(s) + P(f0, f1|s') * P(s'))
            = P(f0|f1,s) * P(f1|s) * P(s) / 
(6)           (P(f0|f1,s) * P(f1|s) * P(s) + P(f0|f1,s') * P(f1|s') * P(s')
            = P(f0|s) * P(f1|s) * P(s) / 
(6)           (P(f0|s) * P(f1|s) * P(s) + P(f0|s') * P(f1|s') * P(s')
           ~= P(f0|s)*..*P(fn|s) * P(s) / 
(7)           (P(f0|s)*..*P(fn|s) * P(s) + P(f0|s')*..*P(fn|s') * P(s'))
           ~= P(f0|s)*..*P(fn|s) / 
              (P(f0|s)*..*P(fn|s) + P(f0|s')*..*P(fn|s'))

The last step needs a little explaining. all the P(s) and P(s') drop out of the equation when we're doing a classifier, since for any piece of evidence, f0...fn, the P(s), the probability of spam occurring, is alway the same across any classification. Since P(s) is constant, and P(s') is (1 - P(s)), it is also constant. Therefore, when we are comparing the values to determine if it belong in the spam or ham category, we can get rid of constants.

The actual hard part about bayesian classifiers is how to estimate the underlying probability distribution. If you've never seen a piece of evidence in training, you're going to say the probability of it occurring is zero, which isn't correct if the evidence shows up during classification. There's various techniques for dealing with this, mostly under the term 'smoothing'. I won't describe the various techniques here, but that should be enough to get you started.

Profanity in code

fuck - Google Code Search

Was just procrastinating and found that it's pretty funny to search for profanities in google code search and see what you come up with.

Hackszine.com: Detecting and reducing power consumption in Linux

Hackszine.com: Detecting and reducing power consumption in Linux

Power consumption was usually something of secondary concern for desktop computer engineers for a while. But not so today. When you're cramming all those transistors in such a small space, operating at high speeds, power definitely becomes an issue. Now that mobile and embedded devices are experiencing their slow infiltration of our daily lives, power should be on the table for improvement. Google has been doing some work for this, and they now build their own power supplies, and even build their data centers where power is cheaper (old news, so I won't link it).

Battery life is one area of computing that really is way behind. I'm still hoping for some feat of chemical engineering to save us...but hopefully, in this time of scarce energy for mobile devices will drive some creative hardware engineering.

I have hope for Facebook being the new Google

Facebook just released facebook marketplace, where its members can sell things, like housing, jobs, or textbooks. Strategically, this makes a lot of sense, since it's something that's actually useful to its members, especially if it ties your social network information into what you want to buy and sell. From the looks of it though, it doesn't do that. But I'm sure someone at Facebook is thinking about it.

Facebook is social networking done right--at least better than any competitors that I've seen. On the surface they might all seem the same; there's a personal profile page, there's a list of friends, and you can send messages back and forth with each other. However, I think there's some critical differences.

MySpace has a larger user base, but it is largely seen by its owners as a platform for media advertising. It's an unsupported assertion, but given its mishmash feature set and large ads, it's hard to think otherwise.

Friendster was the leader for quite some time, but has since lost the attention of the under 25 demographic (anecdotal evidence). Their mistake was adding things that were technically neat, but ultimately made the site too slow to use. It's a lot better now, and people are still using it. But based on the features they've put out it seems like they are interested in helping people publishing media to a user's personal network--using blogs, videos, etc. However, no news trickles of them attracting otaku developers, and I'm sure firing the now founder of Renkoo didn't help win over the hearts and minds of otaku developers.

On the other hand, Facebook is seen by its owners as a platform for technology driven innovation to help keep up social interactions between individuals. I'm not sure when the transition happened, but it was more evident to me after news feeds were released. Now, most people were vehemently opposed to it, but I saw it as two things.

First, it was a feedback mechanism to open up sharing. The more you share about yourself to your friends, the more you appear on their radar, and the more interaction you'll interact/message them. This seems to be inline with the goal of keeping people talking with each other.

Secondly, it was the basis of publishing personal news without even having to push a button. We all gather news about the world, but beyond CNN, there's also another type of news we're interested in--information about what our trusted friends are doing. Blogs lets you publish just by pushing a button. Facebook Mini-feeds lets you publish just by doing what you normally do on Facebook. It's not inconceivable that in the future, you can also publish from your mobile that you have free time to chill out, and people can just join you to hang out because they saw that you were available in their mini-feed on their mobiles.

Facebook is pulling ahead in terms of their feature offerings because they seem to be able to attract developers that are the otaku of programmers that are willing to innovate something that's actually useful to their users. Which other social network puts programming puzzles in their mini-feeds? Which other social network has an API? The alacrity in which they deploy features is stunning as well. They implemented twitter pretty easily by listing their status updates. It is in this way that I see them being a 'new Google'--they are setting themselves up as a hacker's paradise and attracting otaku programmers that way.

When Zuckerberg held out against getting brought out, he was either being greedy or he had future plans on what he would be able to do with a social network. Most of the press criticized him for being the former, but it's looking like it's the latter. As long as Facebook is useful for their users, there's value in the social network data that can be used by future applications. If they can establish themselves as the standard platform from which all social information about an individual is gathered through their API, this world would be a changed place, just as Google changed the world with its technology.

Collateral damage caused by incidental limitations

Arto Bendiken | The Road to Enlightenment Is Littered with Irritating, Superfluous Parentheses:

"Python truly sold me on the benefits of dynamically-typed languages and rapid prototyping. I began to see that many of the sacred GoF design patterns were not, in actuality, grand universal truths of software engineering, but simply collateral damage caused by incidental limitations in the abstractive power and object model of certain manifestly-typed programming languages."

This is pretty much the way I feel about it too. I had spent a good year of someone else's money learning UML and design patterns, and it ends up that the only pattern that is remotely useful with dynamic languages is the observer pattern. All others have fallen away because the problem they solved were no longer problems in dynamically typed languages.

That said, I think that the majority of us come from imperative backgrounds of C++ and Java, and it's probably no way to judge static-typeness. Modern static-typed languages such as Haskell and OCaml probably has more tricks up their sleeves.

Erlectricity: Hi Ruby, I'm Erlang.

Educate. Liberate. - Erlectricity: Hi Ruby, I'm Erlang.People are thinking along the same lines I am, though I have nowhere near the guts at the moment to write a bridger...unless this one sucks.

I think lots of people are excited about the language, though I think that those that are just finding Ruby probably won't look at or touch it for a while longer. "Why do I have to learn yet ANOTHER programming language?" They ask.

In any case, due to Erlang's structure around the Actor Model, it makes algorithms like particle swarm optimization and ant optimization seem pretty exciting. More to come later. In the meantime, enjoy the bridge.

Ruby Snippet: Caching object attributes

Here's another little snippet. I'm not sure if I'm extracting out boiler plate code prematurely, but it seems right.

A good general rule of thumb for refactoring is that one should always call an object for its value, rather than storing object values in temporary variables when you're using the object. Generally, you can get away with setting the value of an object to a temporary variable, and then using that temporary variables for subsequent calculations

# c = Collection.new((0..500).to_a)
collection_sum = c.sum
collection_sum * 3 + 2 # some calculation with the sum
if collection_sum == 4 # some comparison with the sum.
  # do something else
end

You're essentially caching the value outside of the object, 'c'. This is good if 'sum' is an expensive call. However, if the code segment gets large, this method tends to get confusing, especially if you stored it in temporary variables at different times, etc. (Also a good rule of thumb is that your scope should never be bigger than about 10-20 lines) It's better to refer to the value directly from the object.

# c = Collection.new((0..500).to_a)
c.sum * 3 + 2 # some calculation with the sum
if c.sum == 4 # some comparison with the sum.
  # do something else
end

This is not applicable to functional programming languages, since all variables are consts within a scope. But for object-orientated imperative languages, this generally makes for less messy code.

However, performance is a problem, if you have to calculate the sum each time you needed it. An easy solution would be to cache the value. An example would be summing the values across some collection. Normally, that wouldn't be a problem, except if you had hundreds thousand entries. If nothing was added to the collection, the sum would stay the same. If something was added, mark the collection to need updating, and then the next time sum() is called, update the value.

You'd need both a variable to keep track of whether the attribute needed updating, and another variable to hold the result. If you only had one attribute, that'd be ok. If you have more than one, it starts to get a little bit messy. This is where meta programming comes in. I wrote a piece of code that did the bookkeeping of caching attributes for you. You'd use it like:

class Collection
  include AttributeCache

  def initialize
    @array = []
    cache :sum, :initial => 0
  end

  def add(x)
    outdate_sum
    @array << x
  end

  def sum
    cached_sum { @array.inject {|t, e| t += e} }
  end
  
end

The code is simple. In the initialization method, there is a call to cache an attribute, sum. And then in the other methods, you'd mark where the sum would be outdated, and in the actual call to sum, you'd specify what to do to update the sum.

module AttributeCache

  def metaclass; class << self; self; end; end
  
  def cache(attr_name, options)
    instance_variable_set "@#{attr_name}", options[:initial]
    instance_variable_set "@#{:sum}_outdated", true

    metaclass.instance_eval do 
      define_method("outdate_#{attr_name}") do
        instance_variable_set "@#{attr_name}_outdated", true
      end
    end
    
    metaclass.class_eval %Q{
      def cached_#{attr_name}(&block)
        if @#{attr_name}_outdated
          @#{attr_name}_outdated = false
          @#{attr_name} = block.call
        end
        return @#{attr_name}
      end
    }

  end
  
end

The biggest hurdle was to figure out how to define a method that accepted a block with meta programming. The best I came up with was to use class_eval. If you have better suggestions, let me know. tip!

Code quickie: instance_variable_set name in ruby

Normally, you can just set an instance variable to initialize it...but if you're doing some meta programming in Ruby, then you might end up using, eval() or instance_eval(). Or you use instance_variable_set(). But notice! You need the "@" symbol in the first argument:

class SomeClass
  def initialize(var_name)
    instance_variable_set "@#{var_name}", 0
  end
end

Well, it doesn't quite make sense to me, since instance variables implies variables of the instance...So you wouldn't think the call to instance_variable_set requires the "@" symbol in the first argument. Tip!

Defaults and Guards

I was watching the javascript lecture, and it mentioned guards and defaults in javascript, and I realized that it was the same in Ruby, and was something that I've been looking for. I had already known about defaults. If you were coming from a C or Java background, you probably would write it in ruby as:

if !a.nil?
  b = a
else
  b = 0
end

If you were more versed in other more dynamically typed languages, you'd rather write it in ruby as:

b = a || 0

It seems a bit obtuse, but I think this structure is invoked so often in my experience, that the shorthand is actually quite welcome. And it's not too bad once you know what it is.

In Erlang (and I think Haskell), there are guards for a function. Guards are basically a condition that must exist before the function is run. If you were coming from a C or Java background, you'd probabily write it in ruby as:

if !a.nil?
  b = a.some_method()
end

But really, it can be written as:

b = a && a.some_method

or, like

b = a.some_method unless a.nil?

I think the latter is more readable, but there would be no default if 'a' didn't exist. With the bitwise operators, you can chain it:

b = (a.respond_to?(:gsub) && a.gsub(/h/, '')) || "default!"

Now, that's starting to be hard to read. It has a guard for a, so that it doesn't raise an error when it tries to run gsub() if a is nil, and if it is nil, it will return the default. With this kind of thing, you'd want to be judicious and careful when using it. It's definitely easy to go crazy with this sort of thing. Remember, the goal is ease of readability, cuz you only ever write a line once, but you read it lots of times.

Erlang and Neural Networks Part III

I had meant to do more on Erlang more quickly, but I got sidetracked by meta-programming. Here's Part III of Erlang and Neural Networks!

Last time, I did Erlang and Neural Networks Part II. And we saw that neural network is basically made up of interconnected perceptrons (or neurons), and they are basically modeled as a linear combination of inputs and weights with a non-linear function that modifies the output.

Drawing a line in the sand

Classifiers often do very well strictly on probabilities. But often times, we don't know what the underlying probabilities are for the data, and not only that, we don't have lots of training data to build accurate probability densities. One way around that is to draw a line in the data space that acts as the decision boundary between two classes. That way, you only have to find the parameters (i.e. weights) of the line, which is often fewer in number than the entire probability space.

This is exactly what a perceptron does. It creates a decision boundary in data space. If the data space is a plane (2D, or having two inputs), then it draws a line. For higher data space dimensions (4D or more), it draws a hyperplane.

So Why Not Go Linear?

The problem with just using a perceptron is that it can only classify data that is linearly separable--meaning data you can separate with a line. The XOR problem is a simple illustration of how you can't draw a line that separates between on and off in an XOR. Minsky and Papert wrote a famous paper that kinda killed off research in this field for about a decade because they pointed this out.

So to get around this linearity, smart people eventually figured out that they can chain perceptrons together in layers, and that gives them the ability to express ANY non-linear function, given an adequate number of hidden layers.

Shake my hand and link up to form Voltron

Let's try linking our perceptrons together. We're going to add two more messages to our perceptrons:

perceptron(Weights, Inputs, Output_PIDs) ->
 receive
   % The other messages from part II

   {connect_to_output, Receiver_PID} ->
     Combined_output = [Receiver_PID | Output_PIDs],
     io:format("~w output connected to ~w: ~w~n", [self(), Receiver_PID, Combined_output]),
     perceptron(Weights, Inputs, Combined_output);
   {connect_to_input, Sender_PID} ->
     Combined_input = [{Sender_PID, 0.5} | Inputs],
     io:format("~w inputs connected to ~w: ~w~n", [self(), Sender_PID, Combined_input]),
     perceptron([0.5 | Weights], Combined_input, Output_PIDs)
 end.

connect(Sender_PID,  Receiver_PID) ->
 Sender_PID ! {connect_to_output, Receiver_PID},
 Receiver_PID ! {connect_to_input, Sender_PID}.

We would never call connect_to_output() or connect_to_input() directory [1]. We'd just use connect(). It basically just adds the perceptron's process ID to each other, so they know who to send messages to when they have an output.

We can now connect up our perceptrons, but with the way it is, currently, we'd have to send a separate message to each perceptron connected to an input to the network. This is tedious. We are programmers and we are lazy. Let's make a perceptron also double as an source node. As source node simply passes its input to to its outputs.

perceptron(Weights, Inputs, Output_PIDs) ->
 receive
   % previous messages above and in part II

   {pass, Input_value} ->
     lists:foreach(fun(Output_PID) ->
                     io:format("Stimulating ~w with ~w~n", [Output_PID, Input_value]),
                     Output_PID ! {stimulate, {self(), Input_value}}
                   end,
                   Output_PIDs);
 end.

Now we can start creating perceptrons.

64> N1_pid = spawn(ann, perceptron, [[],[],[]]).
<0.325.0>
65> N2_pid = spawn(ann, perceptron, [[],[],[]]).
<0.327.0>
66> N3_pid = spawn(ann, perceptron, [[],[],[]]).
<0.329.0>

Note that we get back three process IDs of the three perceptrons we created. Then we start connecting them.

67> ann:connect(N1_pid, N2_pid).
<0.325.0> output connected to <0.327.0>: [<0.327.0>]
<0.327.0> inputs connected to <0.325.0>: [{<0.325.0>,0.500000}]
{connect_to_input,<0.325.0>}
68> ann:connect(N1_pid, N3_pid).
<0.325.0> output connected to <0.329.0>: [<0.329.0>,<0.327.0>]
<0.329.0> inputs connected to <0.325.0>: [{<0.325.0>,0.500000}]
{connect_to_input,<0.325.0>}

We used N1 as an input node connected to perceptrons 2 and 3. So if N1 is passed a value, N2 and N3 should be stimulated with that value.

69> N1_pid ! {pass, 0.5}.
Stimulating <0.329.0> with 0.500000
{pass,0.500000}Stimulating <0.327.0> with 0.500000

<0.329.0> outputs: 0.562177

<0.327.0> outputs: 0.562177

Hurray! So now, the network's got tentacles, that we can connect all over the place, writhing, and wiggling with all its glee. However, this is currently a DUMB network. It can't classify anything because we haven't told it how to learn anything yet. How does it learn to classify things? It does so by adjusting the weights of the inputs of each perceptron in the network. And this, is the crux of neural networks in all its glory. But you'll have to wait til next time!

(1) Note that the last message connect_to_input() isn't followed by a semicolon. That means every message before it in perceptron needs to end with one. So if you've been following along, the stimulate() message from part II needs a semicolon at the end of it now.

Erlang and Neural Networks Part I
Erlang and Neural Networks Part II
Erlang and Neural Networks Part III

Innovation is force fed; someone get the lube!

In an earlier post, I had talked about what users know and what you know, when it comes to listening to your users. That said, when it comes to building new products, either in another line, or something to replace your old product, you should go back to not listening to your users--at least on the first draft. The act of creation is effectively the effort of one (or the few). At least when it comes to first drafts, too many cooks do spoil the broth. That might be a bit Ayn Randian, but the only thing I've ever heard of where design by committee was successful was the Space Shuttle and the Lunar Lander. (If there's more examples, please enlighten me.)

When you're building a product you're essentially forcing your world view onto others. You're basically saying, "I find this to be a pain. And this is not the world as it should be. As a builder, I can correct it after mouthing off for a while." And this is usually why people don't warm up to innovative ideas readily--someone is shoving their world view in your face. And unless you're someone that has been looking for a solution to the same problem when it's introduced to you, you won't be receptive to it. Even innovative people suffer from this affliction of shortsightedness.

“Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats.” – Howard Aiken

Because innovative products can be so jarring, they should soften the blow a bit--or as others like to call it lowering the barriers. This is where influences from design, gaming, and etiquette can help.

Beyond the current trend of sleek lines, horn-rimmed glasses and black turtle necks of designers, design isn't just about putting a gradient background on your web app, or painting things in pastel colors. Hackers making a product should understand that design is the study of how to best solve communication and usability problems with limiting constraints. What information would the user need to know right this second, and how should you convey it to make it as easy to understand as possible? And from the answers to those questions will emerge a form that is also pleasing to the eye.

Gaming is an avenue more familiar to hackers than design is. However, games are often seen as mere trifles of play reserved for kids--though this is changing. If you've played enough video games and thought about WHY they're fun, will help also, because to bring out the essence of fun in what's normally perceived as tedium will give your product an edge. In the lecture about the ESP game by Luis von Ahn, he laments the fact that there's millions of cycles of human computation wasted. There was 9 billion hours played of solitaire last year (est.). Considering that the Empire State Building took 7 million hours and Panama Canal took 10 million hours, that's a lot of wasted hours. We should be able to put those cycles to good use by making people play games to solve problems that computers can't yet solve. So a symbiosis of humans and computers can be considered a large distributed computer to solve hard problems, such as object recognition in images. You might have played it.

In other web apps, the idea of a collection is a powerful mechanism of play. Social networking sites play on the idea of collecting friends, much in the same way that in Pokemon, you "gotta catch them all!". In others, the idea of a scoreboard is a powerful motivator, as seen on Digg and Reddit.

And last of all, the idea of etiquette seems far removed from being applicable to innovative products. However, no matter how much technology people surround themselves with, we are still social beings and will have social tendencies. Because of that, we expect certain behaviors and interactions between ourselves and our machines. We get mad and frustrated at computers and devices because they're usually not very polite. They stop responding when they're busy doing something, but don't tell you what they're doing. They don't remember what you told them last time and asks us over and over again. And when they don't know how to ask for help when something goes wrong, since the error messages are unintelligible to most users. These are all hallmarks of an annoying person, and were it a real person, I'd have kick them to the curb.

The iPod, and in general, Apple products, are known for their politeness. When I first got an iPod, it was the 5th generation. I was surprised that it stopped the music, if the ear buds got unplugged, and that it turned itself off, after it's been paused for a while. Basically, it knew what was going on, and reacted to it in a fashion that makes sense to its owner. That sounds like the promise of Agent based software hyped so long ago. Maybe it should make a slow come-back.

The sad thing is, computer apps and devices have been annoying us for so long, that we have kinda gotten use to it. I think as research on classifiers become more readily available to programmers as being embedded in the language, and the rising influence of designers in applications, we should see a trend towards more polite products. If you can make a product that is polite, it'll go a long way in gathering fans.

In the end, you want people to use what you build if it has value. And users want to GET THINGS DONE, so they can move on with their lives. All products should solve problems, there's no doubt that it's essential. All other points are moot if your product is useless. But given that it does solve a problem, if it is also beautiful, fun, and polite, it will go a long way in lowering barriers so that we can all have pearls Before Breakfast.

Comments on the death of computing

This article is starts off as a complaint or a lament in the area of edge CS, and probably serves as a warning, though the conclusion is probably not as hopeful or optimistic as it could be. Or it could possibly be the lack of imagination. To start:

There was excitement at making the computer do anything at all. Manipulating the code of information technology was the realm of experts: the complexities of hardware, the construction of compliers and the logic of programming were the basis of university degrees.
...
However, the basics of programming have not changed. The elements of computing are the same as fifty years ago, however we dress then up as object-oriented computing or service-oriented architecture. What has changed is the need to know low-level programming or any programming at all. Who needs C when there's Ruby on Rails?

Well, part of it is probably a lament by the author--presumably a scholar--on the loss of status and the general dilution in the quality of people in the field. And the other part is about how there's nowhere interesting left to explore in the field.

To address the first part, it's well known that engineers, programmers (or any other profession) likes to work with great and smart people. Usually, when a leading field explodes you're going to attract these great and smart people to the field. However, the nature of the field of technology is to make doing something cheaper, faster, or easier. And as technology matures, the more the barriers to entry in the field lowers. And as a result, you'll get more people that couldn't make it before in the field and the average quality of people dilutes. People use to do all sorts of research on file access. But now, any joe programmer doesn't think about any of that and just uses the 'open' method to access files on disk. But that's the nature of technology, and it's as it should be.

The environment within which computing operates in the 21 century is dramatically different to that of the 60s, 70s, 80s and even early 90s. Computers are an accepted part of the furniture of life, ubiquitous and commoditised.

And again, this is the expected effect of technology. Unlike other professions, in engineering one is able to make technology which gives people leverage over those that don't use it. This gives the advantage of acceleration and productivity that's scalable that you won't find in other professions. If you're a dentist, there is an upper limit to the number of patients you can see. In order to be even more productive, you'll need to create a clinic--a dentist farm--to parallelize patient treating and you need other dentists to do that. If you're an engineer, the technology that you build is a multiplier, and you don't even need other people to use the multiplier.

But at a certain point, the mass adoption of a technology makes it cheaper, and hence, your leverage over other people isn't that great, and you begin to look for other technologies to make your life easier or give you an edge over your competition. But these are all applications arguments to CS; while important in attracting new talent, it doesn't address where the field has yet left to go on the edge.

As for whether CS is really dead or not, I think there's still quite a bit of work to be done at the edges. Physics in the late 1800's claimed that there wasn't much interesting going on there until General Relativity blew up in their face. Biology has had its big paradigm shift with Darwin, but there's still a host of interesting unknown animals being discovered (like the giant squid) and I'm sure alien biology or revival of Darwin's sexual selection would help open up another shift. Engineering suffered the same thing in the early 1900's, when people with only a background in electromechanical and steam powered devices thought there wasn't much left to invent or explore, until the advent of computing spurred on by the Second World War.

In terms of near-term computing problems, there's still a lot of work to be done in AI, and all its offshoot children, such as data mining, information retrieval, and information extraction. We still can't build software systems reliably, so better programming constructs are being ever-explored. Also, since multi-core processors are starting to emerge, so better concurrent programming constructs are being developed (or rather, taken up again...Seymour Cray was doing vector processors a long while back)

But I'm guessing the author of the article is looking for something like a paradigm shift, something so grand that it'll be prestigious again, and attract some bright minds again.

In the end, he is somewhat hopeful:

The new computing discipline will really be an inter-discipline, connecting with other spheres, working with diverse scientific and artistic departments to create new ideas. Its strength and value will be in its relationships.

There is a need for innovation, for creativity, for divergent thinking which pulls in ideas from many sources and connects them in different ways.

This, I don't disagree with. I think far-term computing can draw from other disciplines as well as being applied to others. With physics, there's currently work on quantum computers. In biology, there's contribution to biology from bioinformatics and the sequencing of genes, as well as drawing from it like ant optimization algorithms and DNA computers. In social sciences, there's contribution to it using concurrent and decentralized simulation of social phenomenon, as well as drawing from it like particle swarm optimization.

One day, maybe it will be feasible to hack your own bacteria, and program them just as you would a computer. And then, a professor might lament that any 14 year old kid can hack his own lifeform when it use to be in the realm of professors. But rest assured, there will always be other horizons in the field to pursue.

Ruby Quiz #122 Solution: Checking Credit Cards using meta-programming

So this is the first time I actually did a RubyQuiz for real. I spent probably 3 or 4 hours on it. Not too shabby. And, I got to do a little bit of meta-programming! It's basic meta-programming, but I liked the solution. Brief intro to the quiz:

Before a credit card is submitted to a financial institution, it generally makes sense to run some simple reality checks on the number. The numbers are a good length and it's common to make minor transcription errors when the card is not scanned directly.

The first check people often do is to validate that the card matches a known pattern from one of the accepted card providers. Some of these patterns are:

      +============+=============+===============+
     | Card Type  | Begins With | Number Length |
     +============+=============+===============+
     | AMEX       | 34 or 37    | 15            |
     +------------+-------------+---------------+
     | Discover   | 6011        | 16            |
     +------------+-------------+---------------+
     | MasterCard | 51-55       | 16            |
     +------------+-------------+---------------+
     | Visa       | 4           | 13 or 16      |
     +------------+-------------+---------------+ 

There's more rules for each credit card at wikipedia. So normally, how would you do this with OO design? First thing that came to mind was creating a general CreditCard base class, and use polymorphism to implement the rule for each type of card, which is a subclass of CreditCard (i.e. Mastercard extends CreditCard). The problem with this, I've always found is that there's a proliferation of classes when you do something like this. People have solved this problem with other patterns, such as Factories, to build families of classes.

But that's a lot of structure that I didn't want to write for a little RubyQuiz. So I opted for case statements at first:

def type(cc_num)
  case cc_num
  when /^6011.*/
    return :discover if cc_num.length == 15
  when /^5[1-5].*/
    return :mastercard if cc_num.length == 16
  ...other card rules...blah blah blah
  end
  return :unknown
end

But as we all learned from having to maintain a proprietary server program written in C nested 11 or 12 layers deep all in one main file, case statements suck and don't scale (guess who had to do that?). So what's a better solution? I'd like to think I came up with a nice one.

With dynamic programming languages, I find that a lot of the problems that design patterns solve simply go away. And with meta-programming, it can be a much more flexible tool to solve design problems, rather than with design patterns. In a way, I created a very very tiny domain specific language for checking credit card type and validity. All you need to do to use it is define the rules in the table above in your class which subclasses credit card checker:

require 'credit_card_checker'

class MyCreditCardChecker < CreditCardChecker
  credit_card(:amex) { |cc| (cc =~ /^34.*/ or cc =~ /^37.*/) and (cc.length == 15) }
  credit_card(:discover) { |cc| (cc =~ /^6011.*/) and (cc.length == 16) }
  credit_card(:mastercard) { |cc| cc =~ /^5[1-5].*/ and (cc.length == 16) }
  credit_card(:visa) { |cc| (cc =~ /^4.*/) and (cc.length == 13 or cc.length == 16) }
end

CCnum = "4408041234567893"
cccheck = MyCreditCardChecker.new
puts cccheck.type(CCnum) # => :visa 
puts cccheck.valid?(CCnum) # => true

Neat! So this way, you can have any type of credit card checker you want, in any combination. And if suddenly there was a proliferation of new credit card companies, you can add them pretty easily. How is this done? Well, let me show you:

require 'enumerator'

class CreditCardChecker
  def self.metaclass; class << self; self; end; end

  class << self
    attr_reader :cards

    def credit_card(card_name, &rules)
      @cards ||= []
      @cards << card_name

      metaclass.instance_eval do 
        define_method("#{card_name}?") do |cc_num|
          return rules.call(cc_num) ? true : false
        end
      end
    end

  end

  def cctype(cc_num)
    self.class.cards.each do |card_name|
      return card_name if self.class.send("#{card_name}?", normalize(cc_num))
    end
    return :unknown
  end
  
  def valid?(cc_num)
    rev_num = []
    normalize(cc_num).split('').reverse.each_slice(2) do |pair|
      rev_num << pair.first.to_i << pair.last.to_i * 2
    end
    rev_num = rev_num.to_s.split('')
    sum = rev_num.inject(0) { |t, digit| t += digit.to_i }
    (sum % 10) == 0 ? true : false
  end
  
  private
  def normalize(cc_num)
    cc_num.gsub(/\s+/, '')
  end
end

If you don't know much about meta-programming yet, you might want to try _why's take on seeing metaclasses clearly along with Idiomatic Dynamic Ruby. Don't worry if it takes a while...I was stumped for a while also.

Anyway, the magic is in the method credit_card. Notice it's between "class << self" and "end", which means that this method is defined in the singleton class of the class CreditCardChecker. But you can just think of it as a class method. Same thing with the method metaclass(), it is a class function that returns the singleton class of the caller.

Now, the thing is, this isn't very exciting in itself. However, notice that credit_card() is executed in the subclass MyCreditChecker. This means that when inside credit_card(), metaclass returns NOT the singleton class of CreditCardChecker, but the singleton class of MyCreditCardChecker! Then when we proceed to do an instance_eval() and a define_method(), we are defining a new method in the singleton class of the subclass MyCreditChecker. Inside the method, it will call the block that evaluates the rule given for that card. If true, it returns true and false if false. The only reason I did it that way, is so in case the block returns an object, it'll return true instead of the object.

Therefore, to any instance of MyCreditChecker, it will look like there's a class method with the name of the credit card. So if you did:

require 'credit_card_checker'

class MyCreditCardChecker < CreditCardChecker
  credit_card(:amex) { |cc| (cc =~ /^34.*/ or cc =~ /^37.*/) and (cc.length == 15) }
end

MyCreditCardChecker.amex?(cc_num) would be a valid method that checks if the credit card number is an American Express Card. And what cctype() method does is that it cycles through all the known credit cards and returns the first one that's valid. The rest is standard fare, so I won't go through it.

And oh, btw, each_slice() and each_cons() got moved to the standard library, so you have to include enumerator in order to use it--even though the official ruby docs say that it's still in the Enumerables class in the language.

Inconsistent virtual realities for social augmentation

Cognitive Daily: If you want to persuade a woman, look straight at her:

"There is a considerable body of research showing that eye contact is a key component of social interaction. Not only are people more aroused when they are looked at directly, but if you consistently look at the person you speak to, you will have much more social influence over that person than you would if you averted your gaze....Since each individual's virtual experience is generated separately, in a "room" full of people, each person could experience the phenomenon of everyone else looking at them. Everyone can be the center of attention, all at the same time!"

That's an interesting way to view things. I hadn't thought too much about that, since generally, simulations and games work hard to maintain game state world consistency.

But as we know from Horchow and Carnegie, people are interested mostly in themselves. Inconsistent realities to facilitate or even manipulate social interactions is both fascinating and a bit unnerving due to its immediate implications of social engineering, as most modern people in the western world in this day and age believe in free will.

However, I think it can certainly put to good use, especially in terms of customer service, to help make a customer feel like they are getting special and speedy attention. In the future, if there are Non-Player Characters who are store clerks in either augmented or virtual realities, a customer can have the benefit of seemingly personalized attention.

I can see this implemented in a physical store, where a customer walks in and an augmented store clerk helps them out. And if two customers, say two girls out shopping together, are listening to the same augmented store clerk, one can change the image to make it seem like the clerk is addressing them both at the same time.

As for the article's claim of gender differences, the sample size is pretty small, given only 6 male pairs and 6 female pairs for each of the 3 study groups. But the difference between genders are pretty significant in the graph...and I don't see any manipulation of the graph to make results seem more significant than they are offhand.

Adobe open sources Flex, it'd be nice for mobile too

Now that's news. I think it's a good strategy on their part, since there's still work to be done in the adoption phase of user interfaces, both on the web and mobile devices. What is most interesting is if Adobe plans to use some version of Flex as a platform for mobile devices. Currently, it's done in JavaME, and after trying it out, it was hard, because the tools were still a bit inadequate, and the fact that it's still not easy to get applications on to phones.

With an open sourced language for rich/heavy front-ends, I wouldn't be surprised if this gains quick adoption, as I see just OpenLaszlo and Microsoft's Silverlight as being the alternative. AJAX will have to come up with other tricks up its sleeve, like faster javascript engines...This whole scene will be something to keep an eye on, as it'll be interesting how it plays out.

Reconnecting to database server in Rails

I've had more posts up my sleeve, though I haven't had time to actually polish them up. I should make my blog posts go back to its roots, where I just said anything as a first draft. That way, you'll get more stuff. So as usual, I happened across my travels through Rails-land and saw something that I don't think gets seen too often...since I couldn't find it on the first page of Google. It was an error like this:

>> user = Account.find(1)
ActiveRecord::StatementInvalid: Mysql::Error: MySQL server has gone away: 
SELECT * FROM accounts WHERE (accounts.id = 1) from /usr/lib/ruby/gems/1.8/gems/activerecord-1.15.0/lib/active_record/
connection_adapters/abstract_adapter.rb:128:in `log'
...blah blah blah...

Since connections are expensive (in terms of time) to make, web frameworks, and anyone making raw connections to the database, will use the same connection for multiple SQL queries, and close the connection when you're done.

Usually you won't see this in Rails, because it does a pretty good job of maintaining the connection, either per session, or per user action in the controller. However, when you have a background process running using something like BackgrounDrb, if there is no activity between the background worker and the database for a couple hours, the database is going to close the connection, and the worker will still think the connection is valid. In other words, ActiveRecord::Base.connected? will return true.

Here is also where I found a use for 'else' in blocks as mentioned by Jamis Buck. When the connection goes out cold, we can't really tell that its' because it's been sitting there too long. It will raise an ActiveRecord::StatementInvalid, which is the same thing raised when you have a bug during development. As a simple fix, I just wanted something to try reconnecting to the database once, just in case it was only because the connection was cold.

class SomeBackgroundWorkerClass
def initialize
  @already_retried = false
end

def some_database_operation
  begin
    Account.find(1)
    # or some other database operations here...
  rescue ActiveRecord::StatementInvalid
    ActiveRecord::Base.connection.reconnect!
    unless @already_retried
      @already_retried = true
      retry 
    end
    raise
  else
    @already_retried = false
  end
end
end

So, that way, as long as it succeeds every other time, it'll keep on going. Tip!

Log files in XML, YAML, or JSON?

Currently, log files are almost always in a form that is hard for machines to parse. It's either in a comma separated form, or an arbitrary proprietary format. Why is that? The primary assumption of log files is that a human will read it. But usually, no humans read it unless something goes wrong, and it's always in a reactive sense.

Of course, no human wants to look at log files all day long. This is the kind of thing that machines would be great at...if only they could read it. What we can do to help log file processing is to put it into formats that are easily transferable and readable by both humans and machines. Isn't that the primary goal of data formats such as XML, YAML, and JSON? A machine that can read log files can monitor it and do analysis on it to present information to users that wouldn't be apparently when just reading the log file straight through.

And yet, most of our log files are in proprietary formats, especially for web servers and web applications. This might not be as much of a problem for long-standing programs like Apache. They've been around long enough that their log file has stabilized and there are specialized programs to parse and analyze those log files.

In addition, I think (correct me if I'm wrong), JSON format allows you to carry code as if it were data. Having that code to perform specific transformations on the log data when processing it might be something useful. Therefore, it would be like having transformed data transparently available to the parsing/analysis program. It would also cut down on the amount of extra programming that is needed for the analysis program, since the log would know how to generate specific pieces of information not explicitly written in itself.

Code quickie: How to interlace two arrays in ruby

Hrm, I'm not sure whether it's worth posting or not, but I was looking for a way to interlace two arrays in ruby. This is what I came up with originally, and it worked fine for a bit:

class Array
  def interlace(other_array)
    interlaced_array = []
    self.each_with_index { |x,i| interlaced_array << x << other_array[i]}
    return interlaced_array
  end
end

This code has the problem that on arrays of different sizes, it'll either leave off the longer array's remaining elements or insert nils for the shorter array. This isn't a good default behavior. What we'd like is for the longer array, whichever one it is, to get its remaining elements tacked on the end of the interlaced array after the elements in the shorter array have run out.

I decided to do it recursively. I haven't written anything recursive since that post on Erlang.

class Array
  # interlaces an array with another array.  It dovetails the two arrays together.
  # 
  #   [1,2,3,4,5,6].interlace([7,8,9]) # => [1, 7, 2, 8, 3, 9, 4, 5, 6]
  #   
  #   [1,2,3].interlace([1,2,3,4,5]) # => [1, 1, 2, 2, 3, 3, 4, 5]
  def interlace(other_array)
    return other_array if self.empty? 
    return [self[0]] + other_array.interlace(self[1..-1])
  end
end

Great, now it works on different sized arrays! What you'll notice is that unlike most recursions, this one "switch places" with the other array on every recursion with the call, other_array.interlace(self[1..-1]). It's the first time I've seen a recursion like this. It certainly simplifies the code immensely, since you don't have to check for which array is bigger or smaller. Note, however, that this only works because the method is public. The technique doesn't work for private recursion helpers.

While you don't get to use recursion all that often, I find that its solution is often pretty elegant compared to iteration. I think that it will be useful when we start to use more data structures that are more fractal in nature. Currently, we have lists and trees. Hrm, there might be some possibilities here. For now, we'll keep this short, and if I come up with anything on this front, I'll let ya'll know! Tip!

Updating just the join table

Having a model that has a has_and_belongs_to_many relationships with another model affords you the convenience of a bunch of added on methods that get created when you define the relationship. These are all pretty nice. But I found that I had to forgo these methods for a more crude method.

Let's say you have two models, taken from the Rails book: Article and User.

class Article < ActiveRecord::Base 
  has_and_belongs_to_many :users
end

class User < ActiveRecord::Base 
  has_and_belongs_to_many :articles 
end

In order to create a new article and associate it to a user right away, you can use create!:

user = User.find(session[:user].id)
user.articles.create!(:title => "The Art of FizzBuzz")

But sometimes, an article might be linked to other models as well. Let's say that there's a Shelf model, and an Article habtm Shelves too. Then, you'd have to pull something like:

user = User.find(session[:user].id)
shelf = Shelf.find(params[:shelf_id])
article = user.articles.create!(:title => "Go and foobar yourself")
shelf.articles << article

Now, that last line is tricky. It's adding the new article to the articles of a shelf. Technically, it should just be inserting ids in the join model. However, that's not the case. It will ask shelf to load all its articles first, and then update the join table. Now, if you're going to manipulate articles of that shelf later on in the controller method, I think this would be the way to go.

However, if you're importing articles from the net, that might not work so well. In that case you just needed to add the association in articles to shelves in the join table. The current implementation of <<, concat, and push seems to enforce an explicit query for it at least once.

Therefore, if "shelf" has a lot of articles, then you'll experience a large slowdown in importing your articles--for every new article, you're asking the database to return a list of all current articles on that shelf. Database caches common queries, but in this case, it doesn't help, since you're importing a new article every time, which can belong to different shelves. But the time you come back to the same shelve, it may have been cleared from the cache already.

This is very much like Joel's story about Shlemiel the Painter. It's not that <<, concat, push is implemented poorly, but that it's used for a different scenario with different assumptions--that you're going to be doing other things to the collection within the scope of the controller method.

The only solution I've come up with is an ugly one. I created a model out of the join table, and added a method called link. It finds the associated link, and if it doesn't find one, it creates it.

class ArticlesShelves < ActiveRecord::Base
  def self.link(article, shelf)
    find_by_article_id_and_shelf_id(article.id, self.id) || 
      create!(:article_id => article.id, :shelf_id => shelf.id)
  end 
end

This has lowered the importing of articles from a minute and a half for each article belonging to a shelf with lots of articles, to about 0.5 second for each article on a low powered machine. I personally don't like this solution, since it introduces a very specialized model object with only one purpose, rather than a cohesive set of responsibilities.

While it is possible to push the method "link" to both Article and Shelf, I'm not sure exactly how to query for just the join table if the active record counterpart ArticlesShelves does not exist, other than using find_by_sql(). But even then, how do you execute an "insert" SQL query?

If you've got a better solution, let's hear it. :)