Thoughts on the Science of Computing

So, at my present job the primary technology platform is c# and most of the people here are not familiar with closures. I wasn't too familiar with them either until I started looking at the hole in the middle pattern and some of the new features in .net like anonymous delegates. Now that I have been getting familiar them I am finding them the bees knees and I try to use closures and anonymous delegates whenever I get the chance.

Unfortunately, most programmers I run into aren't familiar with these concepts, so I thought I would try and shed some light on this subject and why I find closures and more specifically, anonymous functions cool.

First off, what is a closure? Wikipedia gives a good explanation. The key concept is that a closure is a function with some private variables/state that belong to it, in addition to any parameters or local variables belonging to the function. So I think of a closure as an object like structure that contains a function and some additional state that it can access.

So whats different about this compared with object oriented programming or a regular function? Someone can create an object that has both data and methods that can access that data or one can also create functions with parameters. The power of anonymous functions is that you can get some object like properties in that you can associate data with a function without specifying any class definitions. This allows you to use anonymous functions in places where they aren't expecting a class but instead pass in your function which will also have the state needed for it to run.

Some examples will clarify. Here is a simple example from javascript.


I was dealing with a bug in Internet Explorer where the popup freezes when writing to it. Apparently this is a known issue and the workaround is to limit your writes to the popup and to introduce a delay after launching the window and writing to it. The solution was to use setTimeout function to introduce a delay between popping the window up and writing to it. The problem was that the syntax of setTimeout makes it difficult to pass arguments to the function that it calls after the timeout. One can essentially only call a no argument function or a function with some string parameter built on the fly. But this did not quite meet my needs as I was passing in html. So I found this blog which was passing a closure to the setTimeout function.

I found this very cool in its simplicity. What happens above is that the function call writeToPopup is evaluated and returns an anonymous function. This function also includes the local state of the context where it was created. In this example the variable content is the only such state. So when writeToPopup returns the anonymous function the variable content is accessible in the anonymous function even though it is not a parameter or a global variable.

We could have written the function in a different way.



The only difference here is that the anonymous function is created in a different context so it would have both content and name as state available to the anonymous function.

It takes a while before the power of closures and anonymous functions hit you. They allow you to do things that should be simple without using things like global variables and without defining specific contracts, classes or function signatures. So, next time you want to find a way to attach some state without passing it along as a parameter or object think of closures.

Of course this is only the tip of the iceberg. To really get to know these concepts I suggest trying to solve a problem like writing a factorial function without using iteratation and only uses anonymous functions for recursion. Here is a good article if you want to see the answer.

Typically in data mining you are looking for patterns in data that has already been collected and saved.  In essence, you are looking back in time to discern patterns to either explain what happened or to make future predictions based on that information.

But in some applications one needs to do continuous online processing of data.  This is prevalent in fraud and intrusion detection systems.  In these scenarios, you are often processing and acquiring data in real-time and making decisions based on this new data and past information.  

To assist  in building systems which can support this capability there has been active research into stream processing systems or data managers.  In these systems one can run a query that runs continuously as opposed to a moment at time.  This allows one to build some sort of monitoring system on top of the stream processor.

This seems like a farily new area and I am not sure what the state of the art is, as we typically don't see these capabilities integrated into commercial DBMS systems. 
I have found the following academic projects that deal with Stream Processing.

Stanford Stream Data Manager
Stream Mill
MAIDS

In addition, there appear to be some commercial products that are similar to the above.  If anyone has used any of these systems or built applications on this type of technology, I would be interested to hear about it.

Update

I have found some additional stream management systems so I wanted to update my list here.

Cougar
Aurora
Borealis
Hancock
Niagra
OpenCQ
Tapestry
Telegraph
Tribeca
Gigascope

A new ACM conference, WSDM2008, just finished up this week on Web Search and Data Mining.  I would have loved to attend but was unable to.  For those who are interested in the papers from this conference you can find them here.

Two of the more recent algorithms in the field of machine learning include Support Vector Machines and AdaBoost. I think both are on the order of ten years old or such.

The idea behind AdaBoost is quite simple. One just tries to build a strong classifier from a set of potentially weak classifiers. The idea is to choose the weak classifiers in a way that when combined they perform much better.

One of the classic applications of this technique is Face Detection. Lets say you have several thousand different filters you can apply to an image. You would then just apply each filter to a set of training images some of which have the feature you are looking for and some of which don't. Each filter would output some real number for each of the images. You would then choose a threshold for each filter such that it classifies over 50% correctly. Then just choose the filter with the highest accuracy.

One just repeats this as long as one has more filters to choose or a high enough accuracy is achieved. However at each stage when we choose a new filter we re-weight all the data samples that were correctly classified to have a lesser weight and the incorrectly classified data points to have a stronger weight. So as you progress you find filters that are specific to difficult cases.

There are some mathematically provable facts about error bounds, and papers on how to choose the weights at each step, but this is the basic idea. Probably the hardest aspect of this problem is how do you choose your set of filters or weak classifiers that you want to use.

Here is the classic paper on Face Detection using this technique.

This post is just a silly attempt at the following,  trying to look smart by putting fancy equations on my blog and playing around with latex, and talking about MLE.

Down below is an html version of a portion of a tex file that I generated for a homework. 

I am new to Latex and finding it incredibly useful for formatting documents that include equations or other mathematical symbols.

It also great for general typesetting, for instance, if you want to create a resume that really stands out there are great templates available. 

From my vantage, latex documents work similar to html documents with tags that control various features.  The great thing is that once you get the hang of them it is very easy to type in equations like below.   Here is the latex code for equation 1.

\begin{equation}
\vec{\theta} = (\lambda_1,\lambda_2,...,\lambda_k, Z)
\end{equation}

And similar ideas are used for the rest.  Here is the complete file.

Some blogs and web frameworks actually have renderers that will translate an latex equation directly to a png file dynamically.

Unfortunately, I haven't found anything in asp.net that does this.  So, I actually ran a program called htlatex to generate the png files below of the equations.

Now, for a quick, crude explanation of what's below. 

Maximum Entropy is a conecpt that is very popular in statistics these days.  The ideas is let's say you care about certain statistics about a dataset or problem, for instance you might be interested in the mean of the data and the variance.  And then lets say you want to fit a distribution to the data while preserving those statistics. 

Well, there may be many different distributions that share the same mean and variance, so one idea is to just choose the distribution with the maximum entropy that fits the data and preserves the statistics.  If you actually do the derivation you end up with an expression for the probability like in equation 2 that is a function of a set of phis, which are just your statistics.  So if we just cared about the mean and variance we would have two phis and two lambdas in the equations below.

So, now that you have equation 2 it depends on the parameters lambda and needs to be normalized.  So one still needs to find the lambdas.  One eventually derives equations like 19 which you can use the data to calculate the lambdas. 

This all can be show using the maximum entropy point of view, but we were asked to show that the equations for lambda could also be derived using Maximum Likelihood Estimation or MLE for short.  Here, we are maximizing the probability of the data given our choice of lambdas.  So one tries to find the lambdas for which the probability is a maximum. 

Below is the meat of the derivation.  Nothing earthshattering below.

We want to use Maximum Likelihood Estimation to find the parameters

(1)

We want to maximize the probability of the data given the parameters

(2)

(3)

Here we rewrite the equation as a log-likelihood

(4)

(5)

(6)

(7)

We want to maximize these parameters subject to the constraint that the integral of p(x) is normalized to 1 over all space.

(8)

We then use a Lagrange multiplier to constrain the log-likelihood when maximizing.

(9)

(10)

(11)

Assuming Z is just a parameter or normalization constant that doesn’t depend on x we can move it outside the integral.

(12)

And using equation 8 to replace the right hand term and setting the derivative to 0 we get.

(13)

(14)

(15)

Replacing alpha in equation 10 with -N and setting the derivative to 0 we get

(16)

(17)

(18)

and finally we get substituting equation 2 into equation 18

(19)

I have been away from the blog since school started.  Life always gets more hectic.  This quarter I am taking three course, compiler construction, pattern recognition and machine learning, and an AI class in animats.  

The compiler course is the most demanding of the three because the projects are very time consuming, but very instructive.  The textbook is Modern Compiler Implementation in Java. 

The project we are doing is building a compiler that translates a subset of the java langauge into MIPS assembly code.  This is done in several phases or passes, from syntax and typechecking to building several forms of Intermediate Representations to performing register allocation and finally instruction selection.  The subset includes inheritance and enough of the java features to make these projects challenging.  I would recommend anyone to take a compiler course because a compiler is a large scale project and one of the more studied software problems.  As such many areas of computer science come together in a compiler.  In particular, register allocators use graph coloring algorithms and fix point calculations are used for things like liveness analysis.

The pattern recognition course is the most interesting.  In todays world we have access to massive amounts of data on the internet and in database systems.  Pattern recognition and machine learning are critical to mining this data for useful information.  The course I am taking focuses on Vision in particular but most of the techniques are more broadly applicable.  Some of the main topics that I hope to expand on more in my next article are Bayesian Decision Theory, different representations, and dimension reduction techniques from PCA, MDS, and Local Linear Embedding, to various discriminative techniques such as ADABoost and Fisher Linear Discriminant.  I have to say that these topics resonate with me coming from a Physics background, originally.  I appreaciate some of the mathematic concepts with these techniques, such as trying to find the intrinsic dimensionality of the data or concepts of manifolds.  In addition we spend a lot of time dealing with entropy and other statistical concepts similar to what finds in Statistical Mechanics. 

In my next article, I will delve into some of the specifics of the techniques listed above.  I hope to detail the compiler construction in more detail and also to give more details on some of the Pattern recognition methodologies.

I mentioned the Hole in the Middle pattern in my previous blog article What’s In a Language? So, I wanted to actually use the pattern in C# with anonymous delegates, because that is the platform that I use at work primarily. One of the uses that jumped out was in a database layer. Typically when you are writing a database layer you have boilerplate code in every method to open and close connections and possibly handle exceptions and log exceptions. This is repetitive code that often gets pasted into every method. One approach for doing this is to create a code snippet that you can use from a snippet library. Another is to use the Hole in the Middle pattern.Here is a simple example of the idea:

Now some of you are wondering why go through this trouble when you can use the Microsoft Data Access Application Block. Good question, but the point of this sample is to illustrate one way of using this design pattern.

Now let's take a look at the code. I have created a method ExecuteProcedure that has code to open and close a connection and to handle exceptions. It then fires a delegate of type DatabaseCodeBlock. This is the code block that we supply to fill the hole in this helper function. I am using generics to strongly type the return type of the DatabaseCodeBlock and the ExecuteProcedure method. This is not really neccessary as you could just set the value of a local variable in your anonymous delegate that you could return from the method that is calling ExecuteProcedure, but I think using generics makes for cleaner code.

Now the intersting part of this is the power of the anonymous delegate we are using for the DatabaseCodeBlock. Anonymous Delegates are what are known as closures and they can capture local variables and reference them in the code block. Even if this code block is executed in a another context. This allows one to not have to define different delegate interfaces if you want to use different patterns or to build some parameter array of inputs. Instead, you can just pass in your anonymous delegate and use any local variable in it magically. So in our example we are getting a Customer record by using the local customerKey variable. Now imagine we have a different stored procedure that we want to invoke that requires three or four parameters. If these are in the local scope of where the delegate is created then we can access them. Easy as pie! The last point is a subtle one. I suggest reading up on closures to get a better feel for some of the power of this way of doing things.

Anyone who has a blog should register it with Technorati. To do this however you have to add a link like the above to your site. Technocrati is the google of the blogsphere, with so many blogs registered on their site.

Language preference is a very personal choice among programmers.  What I have found is that either people naturally gravitate towards a language or that one falls into a language on the job or early in one's development as a programmer.

Some would argue that it doesn't really make much of a difference what language you use and other language snobs such as Paul Graham would argue that some languages are inherently inferior to others.  I happen to agree with Mr. Graham, as I have a strong dislike for languages like Visual Basic.  And I truly believe that the language itself shapes and promotes the structure of the programs we develop. 

I am still searching for the perfect language. The main candidates are Ruby, Python, C#, Lisp, and a language from the ML family of languages such as F#. These fall into roughly three different classes of languages, with Ruby and Python both being dynamic/scripting languages, C# being a java/C++ imperative language, and Lisp and F# being more or less functional programming languages.

Of the two scripting languages, I am now leaning towards Ruby as a better option. Although, Python has a much larger community and I like the forced indentation as a way to promote code readability, it lacks certain features that some consider esoteric. In particular Python doesn't have full support for continuations or closures. A continuation is basically a way to jump back in time to previous point in the stack with all the state preserved and continue from point. Some possible applications are controllers for web sites. With continuations, one can reenter the controller at the very next line of code to execute, instead of the beginning of a function. Closures allow you to capture code blocks and the local variables that were set where they are created. The Hole in the Middle Pattern is one example of a use of a closure. Python does have some lightweight support for similar features in the form of generators and single statement closures, but not being an expert in Python or Ruby, I am wary to learn a new scripting language that doesn't support features that I believe will come into more use. Some of the advantages of scripting languages shared by both Python and Ruby are that you can run and debug them interactively in an interpreter. You don't need a compilation phase and they support rapid development which is good for building support scripts and test scripts.

It probably is important for most serious programmers to learn one of the C++ family of languages, whether that is C#, Java, or C++. The main reason is that these have the widest reach right now and if you want a job as a programmer they are always good to know. C++ offers the most performance, Java is the most widely used, and C# is a good option for corporations who like the comfort of being backed by Microsoft.

That being said, unless you are dealing with raw performance as your greatest driver in language choice, I think the general trend in programming languages is more toward functional languages or languages that support some of the features offered by them. C# is grafting on some functional characteristics such as lambda expressions and the yield keyword. But, why settle for features grafted onto a C++ imperative language when one can go straight to source. This is where languages like Lisp and F# come in. I have used Lisp in certain projects in school such as writing a Sudoku solver using constraint satisfaction algorithms and it really got me out of the way I was used to doing things with. What I found, at the end of these projects, was a much cleaner organization had somehow emerged out of my struggling with Lisp. But I have heard interesting things about ML family of languages also like OCAML and F#, so I am now taking a look into them to see how they compare with common lisp.

At the end of the day I would recommend anyone to learn three languages from the three classes, above, a scripting language, a C++ family language, and a functional language. I think I have settled, on Ruby, and C#, and I am still deciding on Lisp or an ML based language.

    Database locking is something that we should all have a good understanding of.  But like threading issues, locking issues can be difficult to troubleshoot and reproduce in different environments.  I recently came upon an issue with a batch process that opened a SqlDataReader to read a large number of data records.  This process was doing work on each record one at a time with the net effect that the SqlDataReader was open for 30 minutes or so.

    The default transaction isolation level in SqlServer is Read Committed, so that when this procedure was run, shared locks are acquired by the SqlDataReader's connection for a set of records.  This caused other processes to fail that wanted to update the same data that the SqlDataReader had locks on, or so we thought.  Are thought was then to change the isolation level the stored procedure to Read Uncommitted or no lock, so that we wouldn't be acquiring shared reader locks and blocking other process from updating.  But before we did this we wanted to demonstrate that Read Committed was an issue here.  To do this we had to figure out just what records were locked and try and update them.

    The complication in this matter is that there are several types of locks in SqlServer such as row locks, table locks, and page locks.  When we looked in query analyzer we saw something like the following when we ran the sp_lock command on spid 77:

    77    9    2135014687    1    PAG    1:3873230           S    GRANT

This id was obtained from the sp_who2 'active' command.  This indicates a page lock, so the command was locking a page of records.  Now in our schema for this table a page holds from 500 to 1000 records so potentially this many records were locked simulatenously.  This can be found from the command dbcc show_statistics which takes a table and index as arguments. 

    Now we wanted to update a record in this group that was blocked to demonstrate failure, because when we just updated a record that we guessed was locked it failed.  We found the following command which helped us read the contents that lived on that page to figure out what records were actually locked.  After looking around I found information on the DBCC Page command.  And issued a command like so,

DBCC TRACEON(3604,1)
DBCC PAGE('DEV', 1, 3873239,3)

The result included the information we needed to identify the records and try and update which failed as expected.  The Sql Server documentation on locking is a bit poor, IMO.  The confusion is with there description of the shared locks and update locks.  A read statement like we were using obtained shared page locks.  These allow others to simultaneously read the same records.  But another connection can also obtain an update lock.  This lock declares an intention to do an update, but you still can't update a record until all the shared locks on the record are gone and the update lock is converted to an exclusive lock. 

Some of the lessons learned were to be aware of locking and concurrency.  In particular, in some cases for large batch processes read uncommitted is appropriate.  Another solutions would have been to go through and read all the records from the SqlDataReader into memory without doing any other processing and then looping through an in memory structure after the reader and connection are closed.  This is essentially what a DataSet does for you behind the scenes. 

Myself and my colleague Wael Rabadi came across this issue in Asp.net 2.0.  I have seen several people with solutions to this problem but with their answers not very clearly explained.  The symptoms of the problem are postbacks not working on pages that have validator controls of some sort.  What is happening is that there is an  IHttpHandler, WebResource.axd, which appears to return the javascript that is used to do these postbacks when using a validator control.  However in most web applications we do some sort of processing in the various handlers in Global.asax.vb, such as Application_PreRequestHandlerExecute.  If these handlers try to access session they will generate an exception because there will be no session available for the request to WebResource.axd.  This is because this Handler does not implement the interface IRequireSessionState.  If an HttpHandler doesn't implement this interface then the asp.net runtime will not provide session for the request and the code in Global.asax.vb will blow up.  The solution is to place some code like the following into your Global.asax.vb, in the Applicatoin_PreRequestHandlerExecute and your Application_AcquireRequestState functions.

If (Not TypeOf HttpContext.Current.Handler Is IRequiresSessionState) Then
      'Do any code that does not require session
Else
    '  Perform any operations that require session.
End If


This code checks whether we should expect session for the handler processing the request.  If not don't do any session operations.  Another approach would be to just check if HttpContext.Current.Session is nothing or not in these functions.
 

    One of the hottest areas in computer science is in the field of Biology.  It seems that so much of the research dollars are going towards genetic research that can hopefully unlock the secrets to diseases.  There is tons of Biological data to be mined for patterns.  One freely available data set is the Gensat data, which contains information about genes in a mouse's brain and the level of expression in these regions.  One type of analysis would try and determine any link between these genes regions with the hope of finding out a possible function for the gene. 

I recently did such an analysis on the data using the LSI methods mentioned in a previous article.  LSI does a singular value decomposition of a matrix.  For this problem I created a genes versus regions matrix and then in each element recorded a numerical value for the strength of the expression in that region. Once the SVD is done, one can map the genes and regions on to two principal components and see what genes and regions lie in the same part of the plot. 

Unfortunately, data mining can be a messy business and my results didn't show anything interesting.  It would be helpful if I had a biologist who could help better guide me on how to interpret the expression levels, patterns.  Another analysis would take into account the age of the mice in question and see how genes vary with age. 

This is often the way with data mining that you have to try several techniques until hopefully you find the pattern or the key to the data, if there is one.

Data Mining is one of the hottest areas in computer science today.  It involves the intersection of several areas, from statistics, database technology, machine learning, and visualization.  And currently there are plenty of tools to process data such as R and the built in functionality in Microsoft Sql Server.  These allow you to do things like build decisions trees to classify data. 

These can be used in Data Mining pipeline which includes data collection, mining, and visualization of the results.  Some of the problems with blindly using these tools is that there are so many different ways to model and mine the data that one needs some knowledge of which models are appropriate for which kinds of data.  And ideally, one should have some metric which can measure the accuracy of the data mining procedure.  Too often, one finds a model which accurately fits some training data but that overfits the data and may not accurately predict.

So how does one Data Mine effectively without falling into these pitfalls?  Good question.  One approach is to get a better understanding of the models that are being applied and in what domains do they work.  What is a Naive Bayes Classifier?  What is a decision tree?  I hope to find some of these answers in a Data Mining class I am currently studying.  The text we are using is The Elements of Statistical Learning. It presents a good overview of many of the models available.  

One of the simplest models is a simple linear model related to least squares fitting.  This may seem like a crude model that wouldn't be effective in general but it is instructive.  Also, there are some interesting things one can do with Linear Algebra.  In particular using the Singular Value Decomposition of a Dataset allows one to remap a set of Data of say n rows and k columns into a new vector space.  The SVD produces the following relation DataSet  = USV' .  Where S are the singular values and U and V can be thought of some type of vectors.  These S values are ordered from largest to smallest.  The idea being that the data spreads out along different dimensions with the strongest componenst containing more information.  One can then remap, the data rows into this new space keeping only 3 of the values from the S vector to allow a mapping of a multi-dimensional data set into 3 dimesnsions.  This article, Using Information Retrieval for Intelligent Information Retrieval, explores some of the ideas of using these techniques for indexing.

Well, this is just the tip of the iceberg, in this field, but I hope to have more later.

I just finished another quarter of graduate school and am not so patiently awaiting grades.  The courses I took include algorithms, operating systems, and reasoning with partial beliefs.   All of them were interesting in their own way.  Algorithms  is  like solving a chess  puzzle.  You wait for the aha moment when the solution pops in your head.  This can be frustrating on a test because you never know how long it will take before this occurs.  If you have seen the problem before it is usually incredibly easy. 

One of the problems on the final was to prove the following problem is NP-Complete.  Is it possible to seat N knights around a table such that no two knights that have a quarrel are side by side.  The solution is to use a hamiltonian circuit and to reduce the finding of a hamiltonian circuit to that of seating the nights around the table.  When feeding the hamiltonian circuit to the knights problem you consider the vertices of the graph as the knights and each pair vertices that are not connected by an edge have a quarrel.  This will show that a hamiltonian circuit reduces to the knights problem.  You still have to show that a solution to the knights problem can be verified in polynomial time which is trivial in this case.

I think everyone knows what an operating system, but it helps to get your hands dirty with the kernel code.  It really seems fairly simple when you get to know the different pieces and Linux is a great platform with the source available to poke around.  In the class we wrote a Virtual File System and a Block device driver in addition to a simple shell.  All very instructive. 

The last class I took was, as I detailed before, about reasoning with partial beliefs and specifically using Bayesian Networks as a formalism to represent causality and to answer queries about a system giving beliefs and evidence.   This has many applications from data mining using a naive bayes model which simplifies notions of independene to genetic modeling of genes.  This area is one of my interestes as I look to specialize in Artificial Intelligence.  There still seems to be lots to be done in these areas as the field is relatively new. 

Now on to next quarter. 

Currently, in one of my classes,  Reasoning with Partial Beliefs, I am learning about Bayesian Networks.  What are they? Probabilistic networks in the form of Directed Acylicy Graphs that can be used to model belief networks.  From these representations one can make various statements about the probability of the various events composing the system given evidence.

I find them incredibly fascinating because they offer powerful ways to model and make statements about various systems.  The applications range from medical diagnosis, to problems involving Genetic linkage and the reliablity of circuts.

The techniques are relatively new in that there was some skepticism about these techniques maybe 10 or 15 years ago, but this no longer the case. 

One can view Bayesian Networks as separate from Computer Science but the linkage is that in most cases computer programs process the Bayesian Networks and give us the answers from the model we input.  The graph representation of these networks also easily lends itself to computer algorithms. 

In a follow up to this article I will provide a simple example of a Bayesian Network and show how it can be used to model something.  Stay tuned.