Regularizations for General Linear Regression

The lasso [Tibshirani, 1996] refers to L1-regularization of linear models:

In group lasso [Yuan and Lin 2006], the D predictors are divided into G groups, and the g-th group has predictors. The regularization term becomes:

,

where denotes the L2-norm: .  So, when all ‘s are 1, group lasso becomes lasso.

A further extension to group lasso is sparse group lasso:

But in practice, we may not need this very complex regularization.

Is Word Segmentation Parallelizable?

I know little about NLP, I read nothing about word segmentation algorithm; however, given my knowledge on hidden markov model and high-order markov model, I though word segmentation is, given

1. a sequence of characters ,
2. a set of words (each word is a sequence of characters), and
3. a language model (first-order transitions between words)

to infer segments in , and get .

If the optimal segmentation is the one maximizing , then it can be solved using dynamic programming strategy.  Use the following notations:

• : the maximal length of a word,
• : the length of string ,
• : the special word denoting the start of a sentence,
• : the special word denoting the end of a sentence.

the dynamic programming solution is as the following recursive process:

1. Start:
2. Recursion:
3. Stop: if , then .

As a tail-recursion, this recursive process can be expressed as an equivalent iteration form: starting by checking the M possible words near the end of the sentence, for each of them, check possible word segmentation at the end of rest sentence.

Alternatively, above procedure can be expressed in an equivalent form: segment the first word at the end of the sentence. This alternative expression results in an iteration starting word segmentation from the beginning of the sentence.

If each processor has the whole language model, it would be trivial to parallelize above procedure. For example, in the Start step, we need to compute M branches before taking . These M computations can be distributed on M processors.

But if the language model is huge and is distributed on multiple processors, it seems difficult (?) to divide-and-conquer the segmentation over these processors with an efficient sharding of both computational structural (iteration steps) and storage structural (parts of language model).

The final question is: usually the sentence is not long, it might not be worth to distribute it over processors for distributed segmentation.

在Mac OS X上运行自由门

在GFW Blog 上有一篇文章，介绍如何在Mac OS X上运行自由门。那个方法需要安装XCode和MacPorts，然后让MacPorts调用XCode编译WINE的源码。其实实在不需要这么复杂，因为有不止一个的为Mac OS X编译好了的WINE，比如WineBottler。利用这些编译好的WINE for Mac OS X，安装就很简单了：

1. 下载和安装WineBottler：一个for Mac OS X的WINE prebuild package。
   下载地址：http://winebottler.kronenberg.org/
2. 下载自由门7.04版（fg704p.exe)。
3. 下载mfc42.dll，放到fg704p.exe同一个目录。
   下载地址：http://dongtaiwang.com/loc/software/dll/mfc42.dll
4. 在Finder里右键点击fg704p.exe，选择“用Wine打开”。

Confidence intervals for parameters of normal distribution

这是我在阅读 Lecture 5 of MIT OpenCourse on Statistics for Applications 的笔记，但是内容多于这个Lecture，因为还包括了同事李玉龙教我的一些内容。

为了估计一个正态分布 的参数： 和 ，我们通常需要一些样本 ，然后用最大似然估计（MLE）：

然而估计都是可能有错的。而confidence interval（置信区间）是比估计更通用的一个概念——正确的估计在这个区间中的概率是 （比如）。

那么 的置信区间分别是什么呢？

定义1 ：If , then

联想1：If , then

定理1：If , then
and

推论1：If , then
(1)
(2)

上面(1)和(2)中， 和 的函数形状都是 x 轴上方隆起一个包。而置信度为 的置信区间就是裁掉函数形状左端和右端面积分别为 的两块，剩下的中间这段区间 。其中 可以通过查函数表得到。

根据(2)，给定一组采样， 都是已知的，只有我们关心的 是未知的。所以根据 就可以得到 。

但是在(1)中，有两个未知参数 和 。如果我们能假设 是已知的，那么我们可以查 的置信区间函数表，用上面类似的办法得到 的置信区间。可是现实中很难假设 已知。此时我们得借用 Student-t 分布的概念和一些数学变形技巧

定义2：If , then

因为(1)所以可以有 ；因为(2)，所以可以有 。代入定义2，得到

(3) 

这里只有 是未知的，所以可以通过查表 得到 ，并且有 ；变形得到

Learning Ranking Using Probit Regression

This SIGIR 2006 poster shows that the learning of a ranking function, given pairwise preferences over a known set of document ids, can be formalized as a specialized probit regression problem.  The idea comes from this 2003 paper, which in addition explained how to solve this specialized probit regression problem using existing statistical software.  (Though, in the case of Web page ranking, I guess no exiting statistical software can be employed.)

For each query, the relevance of document i is denoted by , and given some pairs of

We can estimate by maximizing the likelihood function

If we assume that the relevance weights are distributed normally with mean and variance , then the cumulative density function becomes , the normal cumulative distribution, and the likelihood becomes:

However, my point is that this method is hard to implement in search engine, as it makes use of document ids and clicks on documents, there exist a huge number of parameters (equals to the number of query-document pairs), and relatively a much much less training data set.