Comparing Technologies Inside and Outside Google

Leading positions in some key technological fields have nominated Google the giant in the Internet industry. Now, the open source community and other companies are keeping up with Google in these fields. Here follows a comparison of published Google technologies and those developed outside of Google. I will update this list as I know more.

Development Tools	Inside Google	Outside Google	Remark
Code review	Mondrian	Rietveld	Both Mondrian and Rietveld are written by the inventor of Python
Infrastructure	Inside Google	Outside Google	Remark
Distributed File System	GFS	HDFS	Hadoop's distributed file system
		CloudStore	Formally known as Kosmos file system
File Format	SSTable	String Table	Hadoop's file format of entries of key-value pairs
Distributed Storage	Bigtable	Hypertable	Baidu is a main sponsor of Hypertable.
		HBase	A Hadoop sub-project as an alternative of Bigtable.
Parallel Computing	MapReduce	Hadoop	Hadoop was initiated by guys formally work in Google's MapReduce team.
Remote Procedure Call	Protocol Buffer	Thrift	Thrift was developed by Facebook and is now an Apache project.
Data Warehouse	Dremel	Hive	Hive was developed by Facebook and is now an Apache Hadoop project.
API	Inside Google	Outside Google	Remark
Networking	(I do not know)	boost.asio	boost.asio provides an C++ abstraction to network programming

Learning Boosting

References

1. The Boosting Approach to Machine Learning An Overview, RE Schapire, 2001.
   Schapire is one of the inventor of AdaBoost. This article starts with the pseudo code of AdaBoost, which is helpful to understand the basic procedure of boosting algorithms.

What is Boosting?
Boosting is a machine learning meta-algorithm for performing supervised learning. Boosting is based on the question posed by Kearns: can a set of weak learners create a single strong learner? (From Wikipedia)

Boosting Algorithms
Most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are typically weighted in some way that is usually related to the weak learners' accuracy. After a weak learner is added, the data is reweighted: examples that are misclassified gain weight and examples that are classified correctly lose weight (some boosting algorithms actually decrease the weight of repeatedly misclassified examples, e.g., boost by majority and BrownBoost). Thus, future weak learners focus more on the examples that previous weak learners misclassified.

AdaBoost
The pseudo code of AdaBoost is as follows
As we can see from this algorithm:

1. The weight distribution over training examples changes in each iteration, and the change ratio is determined by alpha.
2. The choose of alpha is not arbitrary, insteads, it is based on the error of weak learner. Reer to [1] for details.
3. The aggregation of weak learners uses alpha to weight each learner.

Emacs Moves to Bazaar

Noticed at Solidot that Emacs has moved their version control to Bazaar, a version control system that can work in traditional centralized way or a brand new distributed way. After going over Bazaar's users guide, I feel that the distributed way is suitable for developers all over the world and working on the same project, because each developer submit code into his local repository (the reason that Bazaar is called distributed) to record his own work, and publish his work via email and SFTP. It is then becomes the responsibility of the maintainer of the main repository to merge individual's work back into the main branch. I may need to read more about this, but anyway, it is interesting.

A Small Computing Cluster on Board

In my previous post, I mentioned a newly developed GPU-based parallel Gibbs sampling algorithm for inference of LDA. Of course, as you know, there are many other GPU-based parallel algorithms that can solve many interesting applications efficiently using NVidia's CUDA programming framework.

More over, by Googling "CUDA MapReduce", you will find MapReduce implementations based on CUDA and GPU, developed by researchers at UC Berkeley, U Texas, Hong Kong Univ. of Sci.&Tech, and etc.

About the supporting hardware, I recently noticed NVidia's Tesla processor board, which contains a 240-core Tesla 10 GPU and 4GB on-board memory. This card can be installed on workstations like Dell Precision T7500. At the time when this essay is written, the price of such a system is about RMB 43,000.

Last but not least, there are significant differences between GPU-clusters and relatively traditionally computer-clusters. Few listed here:

1. There is no mature load-balancing mechanism on GPU-clusters. Currently, GPU-based parallel computing is in the early stage of CPU-based parallel computing, which I mean, no automatic balancing over processors used by a task, and no scheduling and balancing over tasks. This prevents multiple projects from sharing a GPU-cluster.
2. GPU-cluster is based on shared-memory architecture, so it is suitable only for the class of computing-intensive but data-sparse tasks. I do not see more than a few problems in real world that fit in this class.

But anyway, it is not smart to compare GPU-based parallel computing directly with multi-core CPU based solutions, because the latter can be naturally incorporated into multi-computer parallel computing and achieve naturally much higher scalability.

Using Facebook Thrift

While I am looking for a general RPC solution, Thrift comes to my eyes. It is now an Apache project although developed at Facebook. Thrift is very similar to Google's protocol buffer, which was open sourced and hosted on Google Code. For me, Thrift seems support more languages and deployed with a whole set of surrounding support, including thread manager and server/client stubs. More interestingly, Thrift supports exception, that is, exceptions thrown by remote methods can be caught by client code. (I do not remember that Google protocol buffer support this ....)

However, Thrift does not yet have an official tutorial, so, here is a very brief one. (I would resort to an official one once it is published.)

1. Download Thrift from http://incubator.apache.org/thrift
2. Unpack the .tar.gz file to create /tmp/thrift-0.2.0
3. Configure, build and install

   ./configure --prefix=~/wyi/thrift-0.2.0 CXXFLAGS='-g -O2'
   make
   make install

4. Generate source code from tutorial.thrift

   cd tutorial
   ~wyi/thrift/bin/thrift -r --gen cpp tutorial

   Note that the -r flag indicates generating also include files. The result source code will be placed into a sub-directory named gen-cpp.
5. Compile example C++ server and client programs in tutorial/cpp

   cd cpp
   make

   Note that you might want to change the Makefile to tell the lib and include directories where Thrift was installed.

A WordCount Tutorial for Hadoop 0.20.1

Because the document of Hadoop 0.20.1 describes a tutorial program which uses out-of-date APIs, I decided to write the following tutorial for Hadoop 0.20.1. It is notable that in 0.20.1, org.apache.hadoop.mapred.* are deprecated and it is recommended to use org.apache.hadoop.mapreduce.*. This tutorial is based on the new API.

For how to install and configure Hadoop, you might want to refer to my previous post. After Hadoop is installed, let us create a source code directory and put the following Java source file:

package org.sogou;

import java.io.IOException;
import java.lang.InterruptedException;
import java.util.StringTokenizer;

import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.GenericOptionsParser;

public class WordCount {
/**
 * The map class of WordCount.
 */
public static class TokenCounterMapper
    extends Mapper<Object, Text, Text, IntWritable> {
        
    private final static IntWritable one = new IntWritable(1);
    private Text word = new Text();

    public void map(Object key, Text value, Context context)
        throws IOException, InterruptedException {
        StringTokenizer itr = new StringTokenizer(value.toString());
        while (itr.hasMoreTokens()) {
            word.set(itr.nextToken());
            context.write(word, one);
        }
    }
}
/**
 * The reducer class of WordCount
 */
public static class TokenCounterReducer
    extends Reducer<Text, IntWritable, Text, IntWritable> {
    public void reduce(Text key, Iterable<IntWritable> values, Context context)
        throws IOException, InterruptedException {
        int sum = 0;
        for (IntWritable value : values) {
            sum += value.get();
        }
        context.write(key, new IntWritable(sum));
    }
}
/**
 * The main entry point.
 */
public static void main(String[] args) throws Exception {
    Configuration conf = new Configuration();
    String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
    Job job = new Job(conf, "Example Hadoop 0.20.1 WordCount");
    job.setJarByClass(WordCount.class);
    job.setMapperClass(TokenCounterMapper.class);
    job.setReducerClass(TokenCounterReducer.class);
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(IntWritable.class);
    FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
    FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
    System.exit(job.waitForCompletion(true) ? 0 : 1);
}
}  

Then, we build this file and pack the result into a jar file:

mkdir classes
javac -classpath /Users/wyi/hadoop-0.20.1/hadoop-0.20.1-core.jar:/Users/wyi/hadoop-0.20.1//lib/commons-cli-1.2.jar -d classes WordCount.java && jar -cvf wordcount.jar -C classes/ .

Finally, we run the jar file in standalone mode of Hadoop

echo "hello world bye world" > /Users/wyi/tmp/in/0.txt
echo "hello hadoop goodebye hadoop" > /Users/wyi/tmp/in/1.txt
hadoop jar wordcount.jar org.sogou.WordCount /Users/wyi/tmp/in /Users/wyi/tmp/out

Install and Configure Hadoop on Mac OS X

Download and Install

1. Download Hadoop (at the time of writing this essay, it is version 0.20.1) and unpack it into, say, ~wyi/hadoop-0.20.1.
2. Install JDK 1.6 for Mac OS X.
3. Edit your ~/.bash_profile to add the following lines
   

   export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home
   export HADOOP_HOME=~wyi/hadoop-0.20.1
   export PATH=$HADOOP_HOME/bin:$PATH

4. Edit ~wyi/hadoop-0.20.1/conf/hadoop-env.sh to define JAVA_HOME varialbe as

   export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home 

5. Try to run the command hadoop

Run An Example Program
By default, Hadoop is configured to run in a non-distributed mode, as a single Java process. This is useful for debugging. The following example copies the unpacked conf directory to use as input and then finds and displays every match of the given regular expression. Output is written to the given output directory.

cd ~/wyi/hadoop-0.20.1
mkdir input
cp conf/*.xml input
bin/hadoop jar hadoop-*-examples.jar grep input output 'dfs[a-z.]+'
cat output/*

Note that before you re-run this example, you need to delete directory output, otherwise, Hadoop will complain that directory exists.

Some Interesting Ant External Tools/Tasks

AntPrettyBuild

Ant Pretty Build is a tool to easily show and run Ant buildfiles directly from within a browser window. It consists of a single XSL file that will generate, on the fly, in the browser, from the .xml buildfile, a pretty interface showing project name, description, properties and targets, etc. sorted or unsorted, allowing to load/modify/add properties, run the whole project, or run selected set of targets in a specific order, with the ability to modify logger/logfile, mode and add more libs or command line arguments.

Checkstyle

Checkstyle is a development tool to help programmers write Java code that adheres to a coding standard. Its purpose is to automate the process of checking Java code, and to spare humans of this boring (but important) task.

Checkstyle can be run via an Ant task or a command line utility.

Hammurapi

Java code review tool. Performs automated code review. Contains 111 inspectors which check different aspects of code quality including coding standards, EJB, threading, ...

ProGuard

ProGuard is a free Java class file shrinker and obfuscator. It can detect and remove unused classes, fields, methods, and attributes. It can then rename the remaining classes, fields, and methods using short meaningless names.

CleanImports

Removes unneeded imports. Formats your import sections. Flags ambiguous imports.

High-dimensional Data Processing

The three top performing classes of algorithms for high-dimensional data sets are

1. logistic regression,
2. Random Forests and
3. SVMs.

Although logistic regression can be inferior to non-linear algorithms, e.g. kernel SVMs, for low-dimensional data sets, it often performs equally well in high-dimensions, when the number of features goes over 10000, because most data sets become linearly separable when the numbers of features become very large.

Given the fact that logistic regression is often faster to train than more complex models like Random Forests and SVMs, in many situations it is the preferable method to deal with high dimensional data sets.

Native Multitouch for Linux

A research institute in France coworked with Linux kernel developers and created a Linux native muti-point touch tech. I like the following demo video on Youtube:

http://www.youtube.com/watch?v=DTeUbx_nnM4

More details can be found at:

http://lii-enac.fr/en/projects/shareit/linux.html

Skyfire: Mobile Web Browsing over GFW

Just tried Skyfire on my Nokia E71 mobile phone. It is not only able to get over GFW but also able to play Youtube videos (E71 does not have a fully functional Flash player). A colleague told me that Skyfire renders Web pages (including embedded video) on the sever and sends result images to my mobile phone. It is really thin-client, but I will pay a lot for communication to network carrier.

Collapsed Gibbs Sampling of LDA on GPU

Thanks to Feng Yan who sent me his newly published work on parallel inference of LDA on GPU.

The basic motivation is that in the circumstances of GPU, display card memory has too small capacity to maintain a copy of nwk matrix for each core in GPU. So the very basic requirement is to keep a global nwk matrix for all cores. This brings a new requirement that when multiple cores work together in sampling, they should not update the same element of nwk simultaneously. Feng gave a solution to partition the training data by not only documents but also words. This is viable due to the observation that:

• for word w1 in document j1 and word w2 in document j2, if w1!=w2 and j1!=j2, simultaneious updates of topic assignment have no read/write conflicts on document-topic matrix njk nor wor-topic matrix nwk.

Feng also presents a preprocess algorithm which computes an optimal data partition under the goal of load balancing.

A Nice Introduction to Logistic Regression

http://luna.cas.usf.edu/~mbrannic/files/regression/Logistic.html

Among the many text books and tutorials on logistic regression, the very preliminary one given by above link explains how the logistic regression model comes:

In the binary classification problem, it is intuitive to determine whether an instance x belongs to class 0 or class 1 by the ratio P(c=1|x) / P(c=0|x). Denoting P = P(c=1|x) and 1-P = P(c=0|x), the ratio becomes odds P/(1-P).

However, a bad property of odds is that it is asymmetric w.r.t. P. For example, swapping the values of P and 1-P does not negates the value of P/(1-P). However, the swapping does negates the logit ln P/(1-P). So, it becomes reasonable to make logit instead of odds our dependent variable.

By modeling the dependent variable by a linear form, we get:

ln P/(1-P) = a + bx

which is equivalent to

P = e^a+bx / (1 + e^a+bx)

Above tutorial also compares linear regression with logistic regression:

"If you use linear regression, the predicted values will become greater than one and less than zero if you move far enough on the X-axis. Such values are theoretically inadmissible."

This explains that logistic regression does not estimate the relation between x and c, instead it estimates x and P(c|x), and uses P(c|x) to determine whether x is in c=1 or c=0. So logistic regression is not regression, it is a classifier.

Additional information:

• A C++ implementation of large-scale logistic regression (together with a tech-report) can be found at:
  http://stat.rutgers.edu/~madigan/BBR
• A Mahout slides show that they have received a proposal to implement logistic regression in Hadoop from Google Summer school of Code, but I have not seen the result yet.
• Two papers on large-scale logistic regression was published in 2009:
  1. Parallel Large-scale Feature Selection for Logistic Regression, and
  2. Large-scale Sparse Logistic Regression

Clouding Computing Using GPUs

It seems that cloud computing and supercomputing have been in the conversion from massive CPUs to massive GPUs.

In the most recent Top500 Supercomputer list, although most supercomputers still use CPU and Linux, but one of them, the #5, uses ATI RadeonTM RV770 GPUs instead of x86 CPUs.

In a well-known blog post, How Will We Keep Supercomputing Super?, the author claims that due to the limitations stated by the Moore's law, the complexity of CPU makes it costly (in frontend complexity and power consumption) to combine more of them to achieve better performance. On the contrast, it is more technologically reasonable to combine GPUs, which contains more and simpler cores than CPUs.

It is also noticeable that the biggest GPU producer, Nvidia, recently launched their cloud computing product, RealityServer, on Amazon's cloud computing platform.

How to Write a Spelling Correction Program

This is an excellent article by Peter Norvig, a research director of Google.

Emacs — Tab vs. Space

To force Emacs to insert spaces instead of tabs when you press the TAB key:

M-x set-variable indent-tabs-mode nil

Or in your .emacs file:

(setq-default indent-tabs-mode nil)

C++ digraphs and additional keywords

[Original post]

A digraph is a keyword or combination of keys that lets you produce a character that is not available on all keyboards.

The digraph key combinations are:

Key Combination	Character Produced
<%	{
%>	}
<:	[
:>	]
%%	#

Additional keywords, valid in C++ programs only, are:

Keyword	Character Produced
bitand	&
and	&&
bitor	|
or	||
xor	^
compl	~
and_eq	&=
or_eq	|=
xor_eq	^=
not	!
not_eq	!=

To Make Firefox Display PDF on Mac OS X

On Windows, we can simply install Adobe Reader and Firefox will be able to find PDF plugin. However, on Mac OS X, we need to install the PDF Browser Plugin from Schubert|it.

VLHMM for Web Applications

It is glad to find that a WWW'09 paper cited my work on VLHMM (variable-length hidden Markov model). In this paper, Towards Context-Aware Search by Learning a Very Large Variable Length Hidden Markov Model from Search Logs, the authors propose to learn a very-large VLHMM for Web user behavior modeling. I also re-visited my old Web page on VLHMM.

Merge columns from two text files

pr -m -t -s\ file1 file2

Posting Code into Blogger Posts

A concise article describes how to use SyntaxHighLighter to insert program code snippets into Blogger posts.

Bloom Filter

The Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.

Practical applicaitons of Bloom filter including fast test that whether a request could be handled by a server instance, whether a data element is in a replicate in a redundent system.

Be Careful with stl::accumulate

If we are to accumulate a vector of doubles, use the following code snippet:

accumulate(timbre_topic_dist.begin(), timbre_topic_dist.end(), 0.0);

You do not want to be lazy and write 0.0 as 0, which will be interpreted by the compiler as an integer, which is used to infer the type of intermediate and final result of accumulate. For your reference, here attaches one of the multiple prototypes of accumulate:

      template < typename _InputIterator, typename _Tp >
    _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) {
      for (; __first != __last; ++__first)
        __init = __init + *__first;
      return __init;
    }    

Note that the partial result is stored in _Tp __init, which means even we explicitly use plus as the accumulator, the result will still be truncated.

accumulate(timbre_topic_dist.begin(), timbre_topic_dist.end(), 0, // Wrong
plus()); // No effect to correct the mistake.

A Paper on ISMIR 2008

In the following paper published on ISMIR 2008:

• Oh Oh Oh Whoah! Towards Automatic Topic Detection In Song Lyrics, Florian Kleedorfer et al.

the authors present their work using NMF (Non-negative Matrix Factorization) to analyze semantic topics from song lyrics. In Section 3.4:

"We decide to use NMF for automatic topic detection as it is a clustering technique that results in additive representation of items (e.g., song X is represented as 10% topci A, 30% topic B and 60% topic C), a property that distinguishes it from most other clustering techniques."

However, "most other techniques" including pLSA, LDA and Mix-Noisy-OR models all have the "distinguishing property" stated by the authors. In addition, the equivalence between NMF and pLSA has been well studied in the following papers:

• Relation between PLSA and NMF and implications, SIGIR 2006.
• On the equivalence between Non-negative Matrix Factorization and Probabilistic Latent Semantic Indexing. Computational Statistics and Data Analysis 52 (2008) 3913–3927.

The authors also criticize that LSA cannot process large sparse matrices. However, LSA is in fact applying SVD on term-document-matrix (TDM), and there are many SVD algorithms that can decompose large sparse matrices.

A Non-Sense Braille Translator

An apple everyday, keeps doctor away.

I recently wrote a Braille translator, which converts English text into Braille rendered using pretty dots --- only people with well eye-sight can percieve.

Lock Screen in Mac OS X

To enable the "Lock Screen" function of Mac OS X, open your Keychain Access utility in the Applications / Utility folder. In the preference dialog, select "Show Status in Menu Bar." A black padlock will appear in your taskbar in the upper right-hand corner. Close Keychain Access. Now when you click on the padlock, you have a "Lock Screen" option in the drop-down.

Lock Screen in Mac OS X

To enable the "Lock Screen" function of Mac OS X, open your Keychain Access utility in the Applications / Utility folder. In the preference dialog, select "Show Status in Menu Bar." A black padlock will appear in your taskbar in the upper right-hand corner. Close Keychain Access. Now when you click on the padlock, you have a "Lock Screen" option in the drop-down.

解决英文版Windows的中文乱码问题

1. Open "Control Panel"
2. Switch to "Category View"
3. Open "Regional and Language Options"
4. Switch to "Languages" tab
5. Click "Install files for East Asian languages", and click "Apply".
6. Switch to "Advanced" tab
7. In the combo box "Language for non-Unicode programs", select "Chinese（PRC）"
8. Switch to "Regional Options" tab
9. Select "Chinese(PRC)" and "China" respectively for each of the two combo boxes.
10. Click "OK"

Tips: 如果原有的中文软件还是有乱码问题，可以重新安装程序。

Learning OpenCV, the E-book

Learning OpenCV, the E-book

DocView Mode for Emacs

The wiki page.
Shift-+ to enlarge the displaying (.pdf)
C-c C-c to switch between docview mode and text mode

Make Emacs Warns for Long Lines

On Linux, we can use function font-lock-set-up-width-warning to tell Emacs warning for too long lines in source code:

(add-hook 'c++-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))
(add-hook 'java-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))
(add-hook 'python-mode-hook
      '(lambda () (font-lock-set-up-width-warning 80)))

On Mac OS X, above method fails. However, With Carbon Emacs or Aquamacs, we can do as follows:

; for CarbonEmacs (MacOSX)
(defun font-lock-width-keyword (width)
"Return a font-lock style keyword for a string beyond width WIDTH
thatuses 'font-lock-warning-face'."
`((,(format "^%s\\(.+\\)" (make-string width ?.))
 (1 font-lock-warning-face t))))

(font-lock-add-keywords 'c++-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'objc-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'python-mode (font-lock-width-keyword 80))
(font-lock-add-keywords 'java-mode (font-lock-width-keyword 80))

An easier solution for 80-column-rule is lineker. The usage is pretty simple (tested on my IBM T60p, Emacs for Windows): add the following into your .emacs file.

(require 'lineker)
(add-hook 'c-mode-hook 'lineker-mode)
(add-hook 'c++-mode-hook 'lineker-mode)

GCC Does Not Support Mutable Set/MultiSet Iterator

Although C++ STL standard requires that std::set and set::multiset supports both constant iterator and mutable iterator, but libstdc++ supports only the constant one. In /usr/include/c++/4.0.0/bits/stl_set.h (as well stl_multiset.h), we can see the following iterator typedefs:

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 103. set::iterator is required to be modifiable,
// but this allows modification of keys.
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;

This would lead many STL algorithms incompatible with set and multiset. For example, the following code does not compile in GCC 4.0.x:

set myset;             // or multiset myset;
*myset.begin() = 100;  // fails due to begin() returns const_iterator
remove_if(myset.begin(), myset.end(), Is71()); // remove_if invokes remove_copy_if, which requires mutable myset.begin().

It is notable that Microsoft Visual C++ 7.0 and later versions are more restrictive to the STL standard on above issue. Above code works with Visual C++.

Fast Approximate of 2D Water Ripples

Here is a very fast approximation algorithm. The author is really good at observing and finding highly effective approximations, in this case, the value of sine(x+o) is proportional to sine(x), where o is a small phase offset.

Useful Documents for CUDA Development

• Official Programming Guide from NVidia.
• CUDA Programming, a slides from Johan Seland.
  

Make CUDA Works on MacBook Pro

1. Download and install CUDA toolkit and CUDA SDK.
2. When installing the CUDA toolkit, click the Customize button on the Installation Type panel of the installer. Then be sure that CUDAKext is selected for installation. If we do not do this, CUDA applications will complain "no CUDA capable device".
3. After installing add the following to .bash_profile.
   

   export PATH=/usr/local/cuda/bin:$PATH
   export DYLD_LIBRARY_PATH=/usr/local/cuda/lib:$DYLD_LIBRARY_PATH

4. After installing the CUDA SDK,
   

   cd /Developer/CUDA/lib
   ranlib *.lib

   Otherwise, we will get the following linker error when building CUDA applications:
   ld: in ../../lib/libcutil.a, archive has no table of contents
5. Build CUDA sample applications:
   

   cd /Developer/CUDA
   make

   The result application binaries will be installed to /Developer/CUDA/bin/darwin/release.

A useful reference for installation and system requirement is a PDF file named CUDA_Getting_Started_2.2_MacOS.pdf.

A Good Xcode/C++/QuickDraw Tutorial

Xcode C++ Tutorials is a C++ tutorial using Xcode as the development tool and QuickDraw (the 2D graphics engine of Carbon under Mac OS X) as the basic framework. It is good for C++ beginners using Mac OS X, as well developers with experience with other platforms.

Mix Intel IPP with OpenCV

http://software.intel.com/en-us/articles/intel-integrated-performance-primitives-intel-ipp-open-source-computer-vision-library-opencv-faq/

Build OpenCV under Mac OS X

Install OpenCV on Mac OS X

1. Install Xcode on Mac OS X computer.
2. Download OpenCV source package (for Linux) from SourceForge.
3. Unpack the source package
4. Generate Makefile.in/am
   autoreconf -i --force
5. Configure
   ./configure --prefix=/usr/local --with-python --with-swig
   
6. Build and test building result
   make
   make check
7. Install
   make install
   
8. Building applications
   g++ -o capcam main.cc -I /usr/local/include/opencv -L/usr/local/lib -lcxcore -lcv -lcvaux -lhighgui -lml
   

Other sources of information:

• Introduction to programming with OpenCV

Package Management under Mac OS X

Under Windows, we can use Cygwin to manage software packages. Under Mac OS X, we can use Macports. Download and install the Macports dmg file, open a terminal window, and type commands like:

sudo port install cmake

Macports will download the source package and compile it for you.

Note: To make Macports knows the most recent package list, type the following commands regularly:

sudo port -v selfupdate

Note: After installing Macports, open a new terminal windows (program), which will use the system environment variables newly updated by the installation program. Using a terminal window which had been opened before Macports installation will leads to an error complaining cannot find 'port'.

ActionScript 3.0 Mode for Emacs

EmacsWiki suggests an actionscript mode which can be downloaded from a post at PetTomato. After download the .el file, I added the following lines into my .emacs configuration file. This works for my Aquaemacs for Mac OS X.

(load-file "~/.emacs.d/actionscript-mode.el")
(autoload 'actionscript-mode "javascript" nil t)
(add-to-list 'auto-mode-alist '("\\.as\\'" . actionscript-mode))

Gmsh: a three-dimensional finite element mesh generator

Gmsh is an automatic 3D finite element grid generator with a built-in CAD engine and post-processor. Its design goal is to provide a simple meshing tool for academic problems with parametric input and advanced visualization capabilities.

Fullscreen Mode of Aquamacs

We can type Command-Shift-Return to invoke the function aquamacs-toggle-full-frame, which switches between fullscreen mode.  For your customization skills for Aquamacs, refer to http://www.emacswiki.org/emacs/CustomizeAquamacs.

Robust Ray Intersect with Triangle Test

Tomas Moller and Ben Trumbore proposed a robust algorithm in their paper, Fast, Minimum Storage Ray/Triangle Intersection.  A reference implementation of this algorithm can be referred to as http://www.lighthouse3d.com/opengl/maths/index.php?raytriint, which implements the non-culling branch presented in that paper.

Alt and Meta in Aquamacs

The default Meta key in the Aquamacs distribution is Option (and also Esc). If this is unusable for you (your fingers are too well trained on other platforms), you can either press Apple-; (Options → Option Key → Option Key for Meta) to switch to Esc only.

For other interesting things about Aquamacs, refer to Aquamacs FAQ.

Point inside Polyhedron

From the book, Real-time Collision Detection.

Password-less Login Using SSH

Consider we want to login from a MacBook Pro (mbp) to a remote Linux machine (tsingyi), where both computers have OpenSSH installed. In order to make tsingyi trust mbp, we use RSA cryptographic method to generate a public and a private key for mbp, which will be used to identify mbp during login.

To generate the pair of keys, on mbp, type

ssh-keygen -t rsa

Accept all default answers, and we get two files:

~/.ssh/id_rsa     --- the private key
~/.ssh/id_rsa.pub --- the public key

Now, copy the public key file to tsingyi by typing following command on mbp:

scp ~/.ssh/id_rsa.pub wyi@tsingyi:/home/wyi/.ssh/id_rsa-mbp.pub

and add the public key of mbp to ~/.ssh/authorized_keys of tsingyi by typing following command on tsingyi:

cat ~/.ssh/id_rsa-mbp.pub >> ~/.ssh/authorized_keys

Here we are. We should be able to ssh to tsingyi from mbp without typing password now.

Buld OpenGL/GLUT Applications under Mac OS X

Xcode comes with all what we need to build a Cocoa application with OpenGL and GLUT and GCC. So, first of all, we need to install Xcode.

Writing Code

An GLUT C/C++ program for Mac OS X should include three header files:

#include   // Header File For The OpenGL32 Library
#include   // Header File For The GLu32 Library
#include   // Header File For The GLut Library

Note that the locations of these header files in Mac OS X differs from where they are in Linux and Windows (e.g., GL/glut.h)

Building Using GCC

The command line using GCC to build a program main.c is as follows:

gcc -framework GLUT -framework OpenGL -framework Cocoa main.c -o learning

It is notable here that MacOSX uses the concept of so called frameworks. Instead of adding include paths and library names yourself, you add a framework to your compiler call. This is a MacOSX specific extension to gcc.

Building Using Xcode IDE

We can also manage our OpenGL/GLUT projects using Xcode IDE. To create a project, select the project type of "Cocoa Application". To add/edit the code, remove the auto-generated main.m, add a new main.c, and write our code into main.c. To specify the frameworks in IDE, right click the project and choose "Add Exisiting Frameworks" to add OpenGL and GLUT.

Open Source Software on Mac OS X

http://www.opensourcemac.org/
http://www.freemacware.com/
http://www.linuxbeacon.com/doku.php?id=opensourcemac

Simulation of Cracks

The paper: Simulation of the typical Poisson-Voronoi-Cox-Voronoi cell

Multivariate Poisson Models

1. The slides on Multivariate Poisson Models.
   

2. The paper: An Algorithm for Fast Generation of Bivariate Poisson Random Vectors

Crystalization

1. Stochastic and Deterministic Simulation of Nonisothermal Crystalization of Polymers
2. The Structure of Crystals.
   

To Get Forward (Alt-f), Backward (Alt-b) and Delete (Alt-d) Word Works for iTerm

1. Open iTerm.
2. Go to Bookmarks > Manage Profiles
3. Choose Keyboard Profiles on the left and edit the Global Profile
4. Next to Mapping, click the + sign.
5. For Key, choose hex code.
   
6. In the text box next to hex code, enter 0x62 for b, 0x64 for d or 0x66 for f.
   Note that 0x62, 0x64 and 0x66 are ASCII codes for characters b, d, and f respectively.
   
7. For Modifier, check the Option Box
8. For Action, choose send escape sequence.
   
9. Write b, d or f in the input field.

Now Alt-f will jump forward a word, Alt-b jumps backwards a word, and Alt-d deletes a word.

Insert Google Maps and Google Picasa Album into Blog Posts

查看大图

妈妈做的绢花

MATLAB code for Sampling Gaussian distribution

function M = sample_gaussian(mu, Sigma, N)
mu = mu(:);
n=length(mu);
[U,D,V] = svd(Sigma);
M = randn(n,N);
M = (U*sqrt(D))*M + mu*ones(1,N);
M = M';

To Generate Random Numbers from a Dirichlet Distribution

The following code snippet is copied from the MATLAB Topic Modeling Toolbox by Mark Steyvers and Tom Griffiths:

function r = drchrnd(a,n)
% take a sample from a dirichlet distribution
p = length(a);
r = gamrnd(repmat(a,n,1),1,n,p);
r = r ./ repmat(sum(r,2),1,p);

The following is an example that generates three discrete distributions from a symmetric Dirichlet distribution Dir( \theta ; [ 1 1 1 1 ] ):

>> A = drchrnd([1 1 1 1], 3)

A =

0.3889 0.1738 0.0866 0.3507
0.0130 0.0874 0.6416 0.2579
0.0251 0.0105 0.2716 0.6928

>> sum(A, 2)

ans =

1
1
1

Exponential, Power-Law and Log-normal Distributions

• For the standard form of exponential and power-law, refer to Wikipedia.
• For an intuitive introduction to power-law, refer to 幂律分布研究简史.
• For generative models for power-law and log-normal, refer to "A Brief History of Generative Models for Power Law and Lognormal Distributions".
• For how power-law distributions can be generated from random processes, refer to "Producing power-law distributions and damping word frequencies with two-stage language models".
  

Dirichelt Processes and Nonparametric Bayesian Modelling

r.t. An extremely good tutorial for DP. When reading it, take infinite Gaussian mixture model as ab example. After reading it, try to understand HDP.

Questions on DP, CRP and PYP

By Section 4 of [1], it seems that both CRP and PYP produces power-law distributions, where for CRP, the power-law exponent g=1, whereas for PYP it is 1+\alpha.

From the definition of DP, a generalization of Dirichlet distribution, DP should produce multinomial distributions.

But why is the relation between DP and CRP?

References:

1. Producing power-law distributions and damping word frequencies with two-stage language models.

LDA IR

http://www.datalab.uci.edu/papers/fastLDA_2008.pdf said that http://www.datalab.uci.edu/papers/special_words_NIPS06.pdf and http://maroo.cs.umass.edu/pdf/IR-464.pdf have successfully applied the LDA model
to information retrieval and shown that it can significantly
outperform – in terms of precision-recall – alternative methods
such as latent semantic analysis.