Rich Image Captioning In The Wild

In this CVPR 2016 - Deep Vision Workshop paper, we present an image caption system that addresses new challenges of automatically describing images in the wild. The challenges include high quality caption quality with respect to human judgments, out-of-domain data handling, and low latency required in many applications. Built on top of a state-of-the-art framework, we developed a deep vision model that detects a broad range of visual concepts, an entity recognition model that identifies celebrities and landmarks, and a confidence model for the caption output. Experimental results show that our caption engine outperforms previous state-of-the-art systems significantly on both in-domain dataset (i.e. MS COCO) and out-of-domain datasets.

I'll present this work at the CVPR Deep Vision workshop. Hope to see many friends at CVPR this year.

Evaluation of Deep Learning Frameworks

For some reason that I don't even remember, I wrote my comparison of deep learning frameworks (Caffe, CNTK, TensorFlow, Theano, Torch) on GitHub instead of this site.

How Macnix users can stay productive on Windows PCs

So many Mac users nowadays, even at a Windows 10 event

Or why Macbook Pro users should convert to use the new sexy Surface Book  ...

Motivation for this post. 

Microsoft announced a beautiful, hybrid, yet powerful device today. I was stunned by its design. Then I was curious to see what the Hacker News community says. The reaction is overwhelmingly positive. The major concern is perhaps this 

Could be a MBP replacement for developers. The only thing is those of us running on OS X, how is Windows 10? I love my command line and Linux like commands and tools. - Homebrew - Bash scripts - Docker (Windows 10 currently not supported) - Vagrant
I just feel the tooling for MS isn't in the direction I am. I still have a Windows 7 desktop and it's just not the same.

... and unfortunately it's a valid concern. In this post, I'll try to clear that concern. 

For backend developers

From my experience, many backend developers who carry MBPs don't really program for the Mac, or even on the Mac. These people mostly ssh to their dev server and write code to be run on Linux. Even if they write code locally [2], they still need to build or interpret code for the server. So still, their terminal is mostly for ssh to the dev server. 

If you're that person, here's an easy solution to keep you happy on Windows. Install a nice terminal (e.g. ConEmu) [3], Cygwin (with OpenSSH added) [3.5], and then you can have a nice ssh experience on your Windows device. Here's a demo screenshot of my console.

ssh from PowerShell (as a shell environment), which is managed by ConEmu (as a terminal)

Full Linux-server experience, even with tmux and zsh.

If the idea of installing or using Cygwin sounds cumbersome, which shouldn't be, here's a *one-liner * in PowerShell (initial setup only) for your Linux taste.

curl https://chocolatey.org/install.ps1 | iex # install Chocolatey
choco install -y cygwin cyg-get # install apps
cyg-get openssh # install OpenSSH via Cygwin

(Well, I broke the script into 3 lines for explanation, but you get it, don't you?)

You may ask: what is Chocolatey? Aha, it's Windows's answer to Mac OS's Homebrew (or Ubuntu's apt-get) [4]. So, you've already got the Homebrew concern covered [5].

For web-frontend developers

I'm not a frontend guy but I think that those guys may prefer Visual Studio in Windows over any other alternative. VS is really a beast! If you happen to use command lines a lot (in that case you're more likely a full-stack engineer), you can use PowerShell and in case you prefer some of the more mature Unix utilities (as I do), you can always call those commands (in Cygwin's bin).

For iOS developers or iDevices fans

Well, stick with you MBP :). Windows is certainly inferior in this regime.

Conclusions

I don't suggest that you should switch to Windows just because you can also do stuffs in Windows. If you prefer a bare-metal Unix environment, there's no reason to switch to a Windows device (but then, Mac OS may not be your choice either). However, if Unix tooling on Windows is your major barrier for switching to a Windows PC, it should not be anymore.

I emphasized the word PC as I don't see any big deal regarding which OS to use on a laptop/desktop. Note that the same is not true on the server side. Personally, I prefer working with Linux server over with Windows Server (and I haven't seen Mac OS used for servers). But that's another point for another post.

Side notes

[1] Like everybody else, I had not known about this device 

[2] Many people (including me) prefer nice IDEs over vim or Emacs. The files can be synced automatically between the local and the server.

[3] Just as you may prefer iTerm2 over the default terminal on your Mac.
[3.5] Many prefer MSYS2 over Cygwin. I still prefer Cygwin but that's another point for another post.
[4] One of the coolest features of Windows 10, in my opinion, is OneGet. It's a superset of  Chocolatey and Nuget and etc. and it's a built-in command within PowerShell. Unfortunately, it's still beta (that's probably MS hasn't made much noise about it yet) so I still use Chocolatey.
[5] The op also mentioned Docker. Docker is a server side technology, not something that you want to host on your Mac client. So just ssh to your remote machine and docker however you want.

Scaling Up Stochastic Dual Coordinate Ascent

That's our new paper, to appear at KDD 2015. Here's the abstract.

Stochastic Dual Coordinate Ascent (SDCA) has recently emerged as a state-of-the-art method for solving large-scale supervised learning problems formulated as minimization of convex loss functions. It performs iterative, random coordinate updates to maximize the dual objective. Due to the sequential nature of the iterations, it is mostly implemented as a single-threaded algorithm limited to in-memory datasets. In this paper, we introduce an asynchronous parallel version of the algorithm, analyze its convergence properties, and propose a solution for primal-dual synchronization required to achieve convergence in practice. In addition, we describe a method for scaling the algorithm to out-of-memory datasets via multi-threaded deserialization of block-compressed data. This approach yields sufficient pseudo-randomness to provide the same convergence rate as random-order in-memory access. Empirical evaluation demonstrates the efficiency of the proposed methods and their ability to fully utilize computational resources and scale to out-of-memory datasets.

There are two main ideas in this paper

1. A semi-asynchronous parallel SDCA algorithm that guarantees strong (linear) convergence and scales almost linearly with respect to the number of cores on large and sparse datasets.
2. A binary data loader that can serve random examples out-of-memory, off a compressed data file on disk. This allows us to train on very large datasets, with minimal memory usage, while achieving fast convergence rate (due to the pseudo shuffling). For smaller datasets, we even showed that this *out-of-memory* training approach can be even more efficient than standard in-memory training approaches [*].

Note that the second idea is not restricted to SDCA or even linear learning. In fact, we originally implemented this binary data loader for training large neural networks. However, it couples nicely with SDCA as the real strength of SDCA is on very large sparse datasets, for which the need for out-of-memory training arises.

See the full paper for more details :).

Side notes
[*] Cache efficiency is the key, as I mentioned in a previous blog post.

Metrics revisited

Machine learning researchers and practitioners often use one metric on the test set and optimize on a different metric when training on the train set. Consider the traditional binary classification problem, for instance. We typically use AUC on the test set for measuring the goodness of an algorithm while using another loss function, e.g. logistic loss or hinge loss, on the train set. 

Why is that? The common explanation is that AUC is not easily trainable. Computing AUC requires batch training as there's no concept as AUC per example. Even in batch training, we just don't use it as a loss function [1].

I want to ask a deeper question. Why is AUC a good metric in the first place? It's not the metric that business people care about. Why don't we use the true business loss, which can be factored into loss due to false positives and loss due to false negatives, for testing a machine learning algorithm; and even for training it?

The major reason that AUC is favored as a proxy for business loss is that it is independent of the classification threshold. Why are we scared of the threshold? Why do we need to set a threshold in order to use a classifier model? Isn't it anti machine-learning that humans have to manually set the threshold?

So I'd like to propose that we shouldn't consider threshold as a parameter to tune. Instead, make it another parameter to learn. Here are a few challenges when doing so

• If we are using a linear model, this addition of threshold parameter will make the model nonlinear. In fact, we will no longer have linear models.
• The threshold parameter needs to be within 0 and 1. We can relax this constraint by applying a logistic function on a parameterized threshold variable.

ML research has always been challenging. Adding another layer of complexity shouldn't be an issue. Not modeling the business problem directly is more of an issue to me.

Side notes

[1] Computing AUC is costly and computing the AUC function gradient is even costlier.

Is it really due to Neural Networks?

Deep Learning is hot. It has been achieving state-of-the-art results on many hard machine learning problems. So it's natural that many study and scrutinize it. There have been a couple of papers in the series of intriguing properties of neural networks. Here's a recent one, so-called Deep Neural Networks are easily fooled, that was discussed actively on Hacker News. Isn't it interesting?

The common theme among these papers is that DNN is unstable, in the sense that

• Changing an image (e.g. of a lion) in a way imperceptible to humans can cause DNN to label the image as something else entirely (e.g. mislabeling a lion as library)
• Or DNN gives high confidence (99%) predictions for images that are unrecognizable by humans

I myself have experienced this phenomenon too, even before these papers came out. However, what surprised me is many people are too quick to claim that these properties are due to neural networks. Training a neural network, or any system, requires tuning many hyper parameters. Just because you don't use the right set of hyper-parameters doesn't mean that the method fails.

Anyway, my experience shows that the aforementioned instability is likely due to the use of output function, in particular: Softmax. In training a multi-class neural network, the most common output function is Softmax [1]. The lesser common approach is just using Sigmoid for each output node [2].

In practice, they perform about the same in terms of testing error. Softmax may perform better in some cases and vice versa but I haven't seen much difference. To illustrate, I trained a neural net on MNIST data using both Sigmoid and Softmax output functions. MNIST is a 10-class problem. The network architecture and other hyper-parameters are the same. As you can see, using Softmax doesn't really give any advantage.

Sigmoid	Softmax

However, if you train a predictor using Softmax, it tends to be too confident because the raw outputs are normalized in an exponential way. Testing on test data doesn't expose this problem because in test data, every example clearly belongs to one of the trained classes. However, in practice, it may not be the case: there are many examples where the predictor should be able to say I'm not confident about my predictions [3]. Here's an illustration: I applied the MNIST models trained above on a weird example, which doesn't look like any digit. The model trained using Sigmoid outputs that it doesn't belong to any of the trained digit classes. The model trained using Softmax is very confident that it's a 9. 

Side notes

[1] It's commonly said that Softmax is a generalization of logistic function (i.e. Sigmoid). This is not true. For example, 2-class Softmax Regression isn't the same as Logistic Regression. In general, they behave very differently. The only common property is that they are smooth and the class-values using these functions sum up to 1.

[2] Some people say that for multiclass classification, Softmax gives a probabilistic interpretation while Sigmoid (per-class) does not. I strongly disagree. Both have probabilistic interpretations, depending on how you view them. (And you can always proportionally normalize the Sigmoid outputs if you care about them summing up to 1 to represent probabilistic distribution.)

[3] Predicting with uncertainty is very important in many applications. This is in fact the theme of Michael Jordan's keynote at ICML 2014.

NIPS 2014 Highlights

If you didn't go to NIPS 2014, read this great summary by John Platt at Microsoft Research.

Challenges in Machine Learning Practice - Part 1

In this series, I'd like to highlight a few challenges in developing and using a machine learning (ML) system in practice. This first post will focus on model serialization and how to consume a trained model.

The disconnect between training models and putting them into production

What’s the best practice to train and deploy a model?

Most of the major machine learning toolsets and platforms (e.g. SAS, R, Python libraries, Weka, RapidMiner, Hadoop, etc.) focus on providing algorithms and tools to help you analyze and visualize data, extract features, and train models. Once the data scientists are done playing with the data and having trained a good model, how to operationalize that trained model or workflow [1] remains a tricky question to most companies and groups.

What usually happens is one of the following.

1. The whole data mining [2] pipeline is offline. 
1. In some cases, companies just want to get insights from their landfill of data, to help them make more informed decisions. That’s it. They don’t need to or perhaps don’t know how to train/apply a predictive model.
2. Online prediction is not too critical. Some data scientists are willing to run prediction offline on new batches of data. Examples include customer retention analysis, risk analysis, fraud detection (many firms already do fraud detection online but there are still lots of firms running this offline). 
In both cases, machine learning is only for internal use. I’m guessing that the machine learning software market is dominated by these needs but won’t be for long. The future will rely more on predictive analytics.


2. Or after training and validating a model offline, the data scientists will ask other software engineers to implement the model decoder, typically in another language that is more efficient (C++/C#/Java), which can then be deployed as a live service.

(2) is what I want to talk about. There are many problems with this approach.

1. The educational bridge between data scientists (or statisticians) and production engineers. Basically, the data scientists need to explain the model to the engineers. Depending on the complexity of the model and other factors, this process could be long and error prone.
2. Retraining and updating the model is also a pain. After a few months, the data scientists will likely come up with better models, either through retraining with more data or through more fundamental changes. Now the engineers need to update the model. If the change is fundamental, such as switching from SVM to Neural Network, the model decoder would change significantly.


The process of improving the models is and should be endless, at least due to periodic retraining.

If you multiply the cost factors above with the number of projects that use machine learning, the waste of resources is far reaching. It typically takes months and multiple engineers to test and deploy an already trained machine learning model.

Undoubtedly, there are a few solutions out there and they are far from being ideal.

1. Large IT companies (Microsoft, Google, Facebook, etc.) may have the resources to build their own infrastructure to support serializing and consuming models in an automatic way. However, their solutions are (i) internal, (ii) even fragmented within the companies, and (iii) customized for their own data sources/format and their current learning algorithms.
2. Predictive Model Markup Language (PMML) is the most established and common format for serializing machine learning models. Many popular software (such as KNIME, RapidMiner, R, SAS, etc.) [3] support producing models in this format. However, PMML has a few disadvantages:
1. As an old standard, its evolution is very slow. For example, it doesn't support modern methods such as convolutional neural networks.
2. Software that can consume PMML models (e.g. SAS or IBM SPSS Modeler) tend to be expensive and not optimized for online usage.
3. Train a model in a data-friendly environment (let's say Python) and consume the model through that environment [3]. This approach, while fast to make something work, also induces major technical debts that you have to pay later. Some major debts are speed and scalability (both in terms of computation as well as software maintenance).

In summary, producing and consuming machine learning models is still painful for a large number of machine learning practitioners. The current market is very fragmented and still at an early stage. Software that pay attention to producing and consuming models tend to lack other important components to make them widely used. I'll highlight a few of those important components in the next posts.

Notes

[1] It should be noted that almost every predictive model is a workflow, not just a ML-trained sub-model.
[2] Sometimes I use “data mining” to emphasize the practice of mining data just for the sake of understanding but not for making predictions on new examples.

[3] This site provides a comprehensive list of software that can produce and/or consume PMML models.

The importance of cache efficiency in SGD optimization

Recently, some members in our team have experimented with variants of SGD (Stochastic Gradient Descent) and SDCA (Stochastic Dual Coordinate Ascent) on large and sparse datasets (such as the KDD Cup 2010 dataset [*]). Note that we've focused only on linear models (e.g. logistic regression and SVM) which lead to convex optimization.

What we have found during the process is very interesting from the engineering standpoint, yet not covered in any academic papers. That is: in SGD and SDCA, each weights update is typically so fast [**] that cache efficiency can become the limiting factor. Put it another way: we experienced that if the data is randomly shuffled in memory, the algorithm suddenly becomes ~3x slower (see the table below).

The difference between L1 and L2 regularization

Repost of my answer to a Quora question

The difference between \(L_1\) and \(L_2\) regularization is well studied in ML (and you can find lots of reference on the internet). However, the most common explanation is perhaps via this figure.

While it's true (and seemingly intuitive at first), this figure may not be as easy to digest. The figure corresponds to an equivalent constrained optimization problem, but why we need to deal with constrained optimization problem is not clear [1]. In fact, someone asked this question on Quora: What's a good way to provide intuition as to why the lasso (L1 regularization) results in sparse weight vectors?, which motivated me to provide a simpler explanation [2].

ICML 2014 Highlights 2: On Deep Learning and Language Modeling

Previously: Highlights #1 - On ML Fundamentals

Deep Learning and Language Modeling

Images classification seems to be the past. The current wave of DL research is all about language modeling. Here’re some interesting works on this front.

ICML 2014 Highlights 1: On Machine Learning Fundamentals

Abstract

At a high level, Deep Learning (DL) is still hot and DL keeps eating Machine Learning. The conference's attendance distribution was like: half was there for Deep Learning and the other half was there for *Shallow* Learning :). Interestingly, the conference took place in Beijing, for the first time, and more than 50% of the attendants either study or work there (and most of that local population are students). So the attendance distribution could be biased.

In the following, I'll highlight what I've learned and observed from the conference. Here's the outline:

• ML Fundamentals (this post, see below)
• Deep Learning and Language Modeling
• Optimization, Distributed Optimization, and Distributed ML
• Kernel Methods
• Auto ML
• Other Topics

On the imminent decline of MapReduce

Google recently announced at Google IO 2014 that they are retiring MapReduce (MR) in favor of a new system called Cloud Dataflow. Well, the article author perhaps dramatized it when quoting Urs Hölzle's words

We don’t really use MapReduce anymore. 

You can watch the keynote here for a better context. My guess is that no one is writing new MapReduce jobs anymore, but Google would keep running legacy MR jobs for years until they are all replaced or obsolete.

Regardless of what has happened at Google, I'd like the point out that MR should have been ditched long ago.

Someone at Cloudera (the company that used to make money on the hype of Hadoop MapReduce) already partially explained why in this blog post: The Elephant was a Trojan Horse: On the Death of Map-Reduce at Google. Some quotes to remember are:

• Indeed, it’s a bit of a surprise to me that it lasted this long.
• and the real contribution from Google in this area was arguably GFS, not Map-Reduce.

Every real distributed machine learning (ML) researcher/engineer knows that MR is bad [*]. ML algorithms are iterative and MR is not suited for iterative algorithms, which is due to unnecessary frequent I/O and scheduling plus other factors (see the illustration below). For more details on the weaknesses of MR, one can read any intro slides about Spark [**].

Also note that Mahout, the ML library for Hadoop, recently said goodbye to MapReduce.

25 April 2014 - Goodbye MapReduce

The Mahout community decided to move its codebase onto modern data processing systems that offer a richer programming model and more efficient execution than Hadoop MapReduce. Mahout will therefore reject new MapReduce algorithm implementations from now on. We will however keep our widely used MapReduce algorithms in the codebase and maintain them. 

We are building our future implementations on top of a DSL for linear algebraic operations which has been developed over the last months. Programs written in this DSL are automatically optimized and executed in parallel on Apache Spark.

Notes
[*] Unfortunately, lots of companies, including my employer, are still chasing the Hadoop game. Microsoft just less than a year ago announced HDInsight, aka. Hadoop on Azure.
[**] For virtually everything that MR can do, Spark can do equally well and in most cases better. Also note that while Spark is generally fantastic, it is not necessarily the right distributed framework for every ML problem.

What kind of coding skills are required to work on machine learning?

(Image src: Inside BigData)

In our small team of 13 people, who all work on ML, the required coding skills range from

• None (or simple git pull and build). Such person only needs to run experiments and write technical docs. (Revised: perhaps very little to demonstrate how to use the API.)
• to decent numerical computing in MATLAB/Python/R. Such person runs and tweaks experiments on real problems for customers. Knowing at least one of those scripty languages is required so that they can do custom features engineering or visualization tasks that are not supported by the main tool that we build.
• to good C# or F# + great software design + various level of numerical computing. Such person contributes to the main code base.
• to hardcore low level programming. Such person is obsessed with latency/throughput, BLAS, SSE/AVX, GPU, and distributed systems.

Answered on Quora

Highlights of NIPS 2013

Overall

1. Deep Learning (or Deep Neural Network or DNN) is again the most trendy topic of the conference. Its workshop session is perhaps twice (or more than that) as big as the one last year and it was packed for most of the day. Interestingly, Mark Zuckerberg of Facebook stopped by for a Q&A and then a panel discussion session. His visit was mostly to announce the new AI Lab of Facebook. For technical highlights, see below.
2. Distributed machine learning is another topic of great interest.
3. Growing markets and interests in predictive analytics on sensor data (e.g. activity detection on mobile phones or wearable devices), in ML for Health Care, and in ML for Education.
4. And there are certainly bad-ass research in other areas which I have missed. Among the topics of my interest, Optimization (particularly non-convex optimization) however hasn't made much progress.  

Deep Neural Nets

(Image courtesy: http://www.ais.uni-bonn.de/deep_learning/)

• Natural Language Processing. Application of DNN in NLP is the theme of the deep learning research this year. This is natural because NLP is the holy-grail of machine learning research. DNN has already convincingly demonstrated its power in Computer Vision and Speech Recognition. There were some cool research using DNN in NLP such as Compositional Natural Language Parsing with Compositional Vector Grammars by a team at Stanford (led by Richard Socher) and Word2Vec project at Google (led by Tomas Mikolov). I think that this is just the beginning though.
• Computer Vision. New benchmark for ImageNet has been established by Matt Zeiler et al. although it's not a big improvement from the previous record set by Alex Krizhevsky et al. (see their famous paper). Although Matt's work received a lot of attention from the community (come on, he set a new record), I was slightly disappointed. The spirit of his paper is about understanding convolutional neural networks but he did not explain why his network (which is a customized version of Alex's network) yields better results. He also wasn't able to rigorously explain certain mysteries (such as why rectified linear units work so well) in training neural networks.
• Non-convex Optimization. This is the topic that I care the most in DNN because solving a DNN is a non-convex optimization problem. The current techniques only try to find a local minimum, at best. Here's an experiment that my team did for activity detection on mobile devices using sensory data. After features extraction using PCA and feeding the extracted model into a neural network, we got very good results. We then simulated the PCA feature extraction by introducing another layer to the neural network. We expected that the the optimized weights of the first layer should be identical to the PCA weights, if not better. However, we got worse results. This indicates that the optimizer converged to a non-so-good local optimum.

Distributed Machine Learning

There're many interesting posters/talks on the topic of distributed and large scale machine learning at NIPS this year (such as this, this, and this workshop). However, what really excited me is not the work presented at NIPS but Spark, an Apache project built on top of HDFS for running distributed iterative operations distributedly. (It's a shame that I hadn't been aware of this project earlier.)

The cool thing about Spark is that it inherits the goods of Hadoop (i.e. HDFS) and re-engineers the rest. In particular:

1. Iterative algorithms, which is the norm in ML, can be run in memory during their lifetime. No more reading from / writing to the disk for each iteration.
2. Support of more operators, beyond Mapping and Reducing, which can be piped and lazily evaluated. See more here. In a sense, Spark is similar to Parallel LINQ but on HDFS data.

These are the main reasons why serious machine learning practitioners don't use Hadoop beyond HDFS. Yes, stay away from the Hadoop hype. HDFS is cool. The rest of Hadoop is not so.

Machine Learning on Sensor Data

To be (never) updated ...

[C#] Class attributes vs. interface's properties

In C#, attributes are meta-information attached to a code entity (fields/properties, types, or methods). Attributes are generally very useful. However, are they useful on classes? One could argue that instead of using attributes, we can just have that class implement some interface's properties. See the code below for example. Eric Lippert has also advocated for using properties.

Here, I'd like to make a stronger case for using class attributes.

1. Readability: an attribute indicates that the meta-information is static, i.e. it is bound to the class, not instances of that class.
2. Interface doesn't support default values for properties. So any type that implements that interface has to implement all the properties. We can make the properties default in (abstract) classes but not in interfaces but C# (reasonably) doesn't support multiple class inheritance.
3. Attribute may contain logic (see the last example below) while an interface cannot. Furthermore, the same attribute (and any embedded logic) may be used for both type and fields/properties.

Of course, if the meta information is frequently accessed by other code, then we absolutely should use properties because accessing properties is less taxing and also faster (see the example below). 

  1 /* Using attribute */ 
  2     class FriendlyNamesAttribute : Attribute
  3     { 
  4         public string ShortName;
  5  
  6         public string LongName;
  7  
  8         public string HelpText;
  9     } 
 10  
 11     [FriendlyNames(ShortName = "miner") 
 12     class DataMiner  
 13     {  
 14         ... // Class logic here 
 15     } 
 16  
 17     // Accessing the meta-information 
 18     var attr = obj.GetType().GetCustomAttribute<FriendlyNamesAttribute>(); 
 19     if (attr != null) 
 20     { 
 21         var shortName = attr.ShortName;
 22         ... 
 23     } 
 24  
 25 /* Using Properties */ 
 26     interface IHasFriendlyNames  
 27     { 
 28         public string ShortName { get; }
 29         public string LongName { get; }
 30         public string HelpText { get; }
 31     } 
 32  
 33     class DataMiner : IHasFriendlyNames
 34     { 
 35         ... // Class logic here 
 36  
 37         public string ShortName { get { return "Miner"; } } 
 38  
 39         public string LongName { get { return null; } }
 40  
 41         public string HelpText { get { return null; } }
 42     } 
 43  
 44     var friendlyObj = obj as IHasFriendlyName;
 45     if (friendlyObj != null)
 46     { 
 47         var shortName = friendlyObj.ShortName;
 48         ... 
 49     } 
 50  
 51 /* A slightly more complex FriendlyName attribute */
 52     public abstract class NameAttribute : Attribute
 53     { 
 56         public string ShortName; 
 57         public string LongName;
 59  
 60         private static Regex _shortRegex = new Regex("[a-z]"); 
 61         private static Regex _longRegex = new Regex("(?<=[a-z])([A-Z])");
 62  
 63         /// <summary> 
 64         /// Given a field/class name, automatically shortify it
 65         /// </summary> 
 66         public string GetShortName(string rawName)
 67         { 
 70             ShortName = ShortName ?? _shortRegex.Replace(rawName, "");
 73             return ShortName; 
 74         } 
 75  
 76         /// <summary> 
 77         /// Given a field/class name, automatically prettify it
 78         /// </summary> 
 79         public string GetLongName(string rawName)
 80         { 
 83             LongName = LongName ?? _longRegex.Replace(rawName, " $1");
 86             return LongName; 
 87         } 
 88     }

Neural Network Best Practices

I have been ecstatic by work. That's why this blog doesn't get updated as often as I want.

Recently, I have been focusing on the implementation of a state-of-the-art (in both accuracy and speed) and generic neural net, as a predictor for a general ML software. I have learned a ton while doing it and would like to share some of the best practices when implementing a deep neural net [1].

(Image courtesy: http://www.ais.uni-bonn.de/deep_learning/)

1. Neural Nets Basics

The basics of Neural Nets (NN) is well written on Wikipedia. There's no point to repeat what Wiki has already covered. 
However, there are some subtle points that are worth mentioned.

1. Misconception: backprop is not the training algorithm for neural network. It is just a method to compute the weights gradient using chain rules. I have explained it in slightly more details here.
2. Tips: Implementing backprop correctly is key to have a correct neural net implementation. It's easy to have bugs in the implementation when you introduce more complex connection types (e.g. convolutional, pooling, etc.) or other tricks (e.g. dropout). As backprop is one way to compute the gradient, always use another method to assert (when running in debug mode) that your gradient computation is correct. The standard gradient checking method is to use finite difference to calculate the gradient and compare that with the results obtained from backprop.

2. Major techniques to improve prediction accuracy

2.1. Convolutional Neural Networks (CNN)
Just a couple of years ago, convolutional network was considered a trick. Nowadays, it has become the norm to obtain good results in areas such as computer vision and speech recognition, where data has some spatial or temporal structure.

You can read more about CNN here or check out my slides.

2.2. Regularization
Neural net is notorious for being prone to overfitting, due to its massive number of parameters (a.k.a. large capacity). A simple but effective way to prevent overfitting is using dropout. Dropout is a clever use of model ensembling in a large neural net. You can read more about it in Hinton's paper. Implementing dropout is quite simple and we have seen great gains from using it.

2.3. Choice of activation function Sigmoid and Tanh are the two most commonly used activation functions. However, they are not necessarily good choices as activation functions for the hidden units. The reasons are:

• They saturate quickly when the output value is not a narrow region (around 0), i.e. the derivative almost vanishes. This means that the network easily gets stuck or converges slowly when the pre-activated values fall outside of the region. 
• There's no reason that the hidden units should be restricted to (0,1) as in the Sigmoid function or (-1,1) as in the Tanh function.

Rectifier is becoming popular as an activation function. However, I find its theory dubious and my experiments have not shown that it is always better. That said, I'm experimenting with new activation functions. (Little trivia: I'm borrowing many ideas from my graduate work in computational wave propagation.)

3. Speed things up

This is what I want to talk about more because academic papers tend to focus on accuracy and ignore the efficiency aspects.

3.1. Use a highly optimized BLAS Library
The computations at each layer in a neural network can be abstracted as matrix multiplications

• Forward propagation: \(y=W^{T}\times x\)
• Back propagation: \(\nabla x=W\times\nabla y\)
• Weights update: \(W \leftarrow W+\alpha\times x\times \nabla y^{T}\)

where

• \(W\) of size \(m\times n\) is the weights matrix,
• \(x\)  of length \(m\) represents the source layer's nodes,
• \(y\) of length \(n\) represents the destination layer's nodes,
• and \(\alpha\) is the learning rate (assuming that we are using stochastic gradient descent).

Note this abstraction assumes that the source layer contains the bias node, which is 1 [2]. For these matrix operations, it's recommended use a highly-optimized BLAS library such as Intel MKL [4] for running on CPUs or NVIDIA's CuBLAS for running on GPUs. The speed gain from abstracting the operations as matrix multiplies and using optimized BLAS libraries is very significant (tens to hundreds fold faster).

3.2. Convolution Unrolling
Here, I assume that you are already familiar with convolutional network mentioned above and have implemented a basic one. If so, you would notice that the matrix multiply abstraction above doesn't seem to apply. Furthermore, the convolution operations are also slow due to index indirection.

Actually, with the convolution unrolling technique, proposed in this paper by Patrice Simard and John Platt, you can abstract the operations in training a convolutional network as matrix-matrix multiplies.

The layer-wise operations can be described as followed.
$$\begin{array}{cccc}
\mbox{Forward propagation:}\hspace{1em} & Y & = & W^{T}\times X\\
\mbox{Back propagation:}\hspace{1em} & \nabla X & = & W\times\nabla Y\\
\mbox{Weights update:}\hspace{1em} & W & \leftarrow & W + \alpha\times X\times\nabla Y^{T}
\end{array}$$
where

• \(W\) is the weights matrix of size \(k\times m\). Each column of \(W\) corresponds to a kernel and with this layout, the last bias row can be omitted conveniently in the backprop.
• \(X\) is the unrolled input of size \(k\times n\). Each row of \(X\) corresponds to a window in the original input.
• \(Y\) is the output matrix of size \(m\times n\). Each row of \(Y\) corresponds to the output features for a particular feature map.
• \(\nabla X\) is the unrolled (i.e. pre-accumulated) errors of the input layer.
• \(\nabla Y\) is the errors of the output layer.

Here,

• \(m\) is the number of feature maps (map count);
• \(n\) is the number of output features per map;
• \(k\) equals the kernel size plus one (the bias term).

Rolling and unrolling
In order to represent as above, we need two extra steps.

1. Unroll the input vector/matrix in each forward propagation. This process, which involves duplication of many elements, is to store \(X\) contiguously in memory.
2. Roll (accumulate) the back-propagated errors matrix \(\nabla X\) to a flat errors vector (of size equal the source destination), which can then be passed to the earlier layers.

The rolling and unrolling can be done efficiently by pre-computing the index map which maps from the original space to the unrolled space and vice versa.

3.3. More Parallelism
MKL (or CUDA for GPU computing) already does a lot of parallelism. However, there are still parallelism opportunities left on the table.

Due to the high cost of a high performance CPU cluster and due to the inter-machine communication inefficient, we'll focus our parallelism effort on a single machine with multiple GPU cards.

To be continued...

Notes
[1] There're many tricks in NN. There're even conferences (such as ICLR) dedicated to new little techniques. Here, I'll only highlight some major ones that work in almost all situations and sometimes yield significant gains in accuracy and performance. Also, this post focuses on implementation tips, not the theory.
[2] A traditional approach is to treat biases as another set of parameters.

How to understand back propagation algorithm in Neural Networks

I'm not pleased with how back propagation is explained on the internet (e.g. this one). They mistakenly view backprop as gradient descent, or an optimization algorithm, or a training algorithm for neural networks. It is not.

Backprop is simply a method to compute the partial derivatives (or gradient) of a function, which has the form as a function composition (as in Neural Nets). When you solve an optimization problem using a gradient-based method (gradient descent is just one of them), you want to compute the function gradient at each iteration.

For a neural network, the objective function has the form of a composition. How do you compute the gradient? Two common ways to do it.

1. Analytic differentiation. You know the form of the function. So just compute the derivatives using the chain rule (basic calculus). The long mathematical formulas in tutorials or in papers may look scary (because multivariate calculus usually looks ugly). However, if you write down the differentiation steps yourself, you should find that it is very straight forward.
2. Numerical differentiation using finite difference. This method is computationally expensive because the number of function evaluation is O(N), where N is the number of parameters. This is expensive, compared to analytic differentiation. Finite difference, however, is commonly used to validate a backprop implementation, for debugging purpose.

To summarize: backprop is the straightest way to compute the partial derivatives of a function, using the chain rule. It is really first year Calculus plus proof-by-induction plus a lot of patience :).

Highlights of NIPS 2012

NIPS 2012 is the first conference in Machine Learning [1] that I've attended and it was well worth the time and money invested. Here are my brief-but-not-so highlights of the academic contents of the conference and workshops [3, 4].

Overall

1. The workshop sessions were amazing with many interesting topics and talks. They offer both breath (variety of the workshops) and depth, with plenty of time for interactive discussion.
2. Deep Neural Networks (DNNs), not surprisingly, received a lot of buzz and attention [5]
3. Besides DNNs, here are some major topics at NIPS this year.
• Latent Variable Models. The truth is: this is not a topic that I'm yet familiar with. The good thing is: after this conference, I know that there is quite a lot of interest in this topic. Another good thing: there seems to be a lot of numerical mathematics in this research that I am actually familiar with. Anyway, this is a topic that I'll definitely investigate soon.
• Kernel methods: this and this workshop
• Graphical Models and Probabilistic Programming
• ... and perhaps some other cool topics which I have missed.

Deep Neural Nets

(aka. Deep Learning, to a bunch)

• Mathematical Foundation. There are plenty of reasons for the hype in deep networks, which I won't describe here. One of the major academic interests in DNNs at the conference is about its theoretical foundation. Deep networks work so well against many benchmarks but no one can give a solid explanation why. This lack of a mathematical/statistical foundation for deep networks (or neural networks in general) was questioned many times during the conference and the workshop. Fortunately for the field, as Yann Lecun mentioned in the panel discussion, it has recently attracted the attention of some well-known applied mathematicians (such as Stan Osher and Stephane Mallat).
• Why it works well. To me, the fact that neural networks with many layers perform well can simply be explained by its ability to use many parameters. Basically, deep networks allow you to fit a training set, in a nonlinear way, with a bunch of parameters. Loosely speaking, the more parameters you use, the better you can fit the data.
• Overfitting issue. Of course, when you use so many parameters, overfitting will be a concern and it is true that deep networks are prone to overfitting. That's why there was a talk by G Hinton, the master of the art, about dropout technique in neural networks, which targets the overfitting problem.
• Fine tuning. It makes sense from the above that there is a lot of engineering (e.g. fine tuning) in designing a deep network. If we connect all the dots, there seems nothing particularly new or interesting about DNNs. The basic idea is: use a lot of parameters, if you have the computational resource to do so, and engineer the network so that overfitting can be reduced.
• Distributed DNNs. Another hype about DNNs is the distributed work by Google. Along with the mathematical foundation research, distributed DNNs will be a major research direction.
• Here is my fun hypothesis: if your method performs (slightly) better than the benchmarks, its hype will ironically be an increasing function with respect to its complexity and the required computational resource (e.g. 16000 cores and a new parallelism architecture will generate a great deal of hype).

Kernel Methods

Despite the hype about DNNs, kernel methods is still a relevant and is a powerful class of methods (and with strong mathematical foundation). The major focus of kernel methods research is now on low-rank approximation of the kernel matrix, which I'm also pursuing.

• The fact that Leslie Greengard, a computational physicist well known for his co-invention of the Fast Multipole Method and who hasn't worked at all in machine learning, was invited to give a talk at NIPS 2012 is an indication of its importance.
• Unfortunately, he couldn't come at the last minute due to injury, and his talk was replaced by ... well, a deep learning talk (by G Hinton's).
• Even with the absence of Leslie Greengard, there were still more than one talk (one by Francis Bach and one by Alex Smola) about low-rank approximation methods.

Graphical Models and Probabilistic Programming

Disclaimer: I've recently learned about graphical models and here are my takes about this approach.

• Strength: it is the most natural and most accurate way to infer the distribution of an unknown from the observed data, if you can construct the graph that represents the probabilistic relationship of the variables.
• Weakness: this condition is the main weakness of the graphical model. You cannot just throw in features and data and hopefully get a model back. You have to construct a features graph. In many problems where there are a lot of features (or variables), it's hard or even impossible to construct such a graph. In those problems, we don't even know how variables correlate.

That said, graphical models is a powerful way of modeling if the number of variables is not too large and if we want to inject domain knowledge about the data. I think that there are even more problems of this type than very large scale problems.

Unsupervised vs. Supervised Learning

• Unsupervised feature learning. In his talk, Andrew Ng said that Deep Learning is sort of a misnomer. What people should care about is unsupervised feature learning, not deep this or deep that. I agree with him on this. I further think that unsupervised feature learning should be decoupled from deep networks (aka deep learning). 
• It may be possible that deep networks is the current best technique for unsupervised feature learning. However, it is not the only technique or even the first technique. For example, people have used PCA (or Kernel PCA for nonlinear analysis).
• Unsupervised feature learning is not the only application of deep networks. Some recent successes in deep networks are just straight supervised learning from the data (without the pre-training, i.e. unsupervised feature learning).
• Unsupervised vs. Supervised Learning. This is a topic of frequent debate at the conference.
• Arguments for supervised learning: you can get much more information from labeled data
• Arguments for unsupervised feature learning: you can learn more from more data and the amount of unlabeled data is huge compared to labeled data
• Semi-supervised learning. Both sides are valid and here's my take: we should do both unsupervised and supervised feature learning simultaneously, or so-called semi-supervised learning.

----------------------

[1] For those who haven't heard of NIPS, it's one of the main annual conferences (if not the main conference) in Machine Learning.

[3] Disclaimer: this analysis is through the lenses of a computational-mathematician-convert, who has recently been very interested in machine learning.

[4] Not to mention that the whole conference was very well organized. Kudos to the organizers.

[5] Just in case you wonder why it is not surprising, see the media hype: here, here, or here.

Dimension reduction in machine learning

An application of dimension reduction in face recognition. Instead of using thousands of pixel to capture a face image, we can use ~100 eigenface images that when combined linearly can reasonably approximate any face image.

Here's the standard definition of dimension reduction, which I copy from Wikipedia. 

In machine learning (or data analysis in general), dimension reduction is the process of reducing the number of random variables under consideration, and can be divided into feature selection and feature extraction.

Why is dimension reduction important in data analysis? In layman terms, dimension reduction is the process of filtering noisy signals and keep only high quality signals, with or without transforming the original signals. (Dimension reduction without transforming the input signals is typically called variable or feature selection while dimension reduction with transformation is often called feature extraction.) Dimension reduction thus has two main benefits:

1. Better accuracy. By learning from high quality signals, you can predict on new data more accurately by reducing overfitting. 
2. Performance, performance. You can analyze data more quickly in lower dimension. This may be crucial when you have to deal with lots of data.

This is just an introduction of my series on dimension reduction. In future posts, I'll write about:

1. Feature selection methods
• Filter methods
• Wrapper methods
• Embedded methods
2. Feature extraction methods
• Principal component analysis (PCA)
• Fisher linear discriminant analysis (LDA)
• Other nonlinear methods

Feature extraction methods tend to be more powerful, in general settings, and are also harder to understand/implement. Familiarity with linear algebra and matrix decomposition (e.g. eigenvalue or singular value decomposition) is extremely useful in understanding PCA or LDA or machine learning in general.

-------------------------

Note that none of what I'm writing in this series is new. Instead, I just present them in a way that hopefully has some values to certain readers. Of course, instead of writing everything in my own words, I'll reuse as much public material as possible, where I see fit.