Tips on Machine Learning

Machine learning(ML) is a very famous topic in CS now. Lots of applications are based on Machine learning. For example, NLC(natural language computing), data mining, categorization are all related to ML. Actually, nowadays, ML is quite largely based on probability and statistcs. that's why I am revisiting probility model recently.
I'm a freshman in ML, but recently i have some special feelings on this topic.
Last week, i joined a match held by topcoder.com. I have got 1 week to solve especially one problem. it's a problem of gambling. In the problem, you are required to write a gamble machine who play a special card game with server. Then your score will be measured by how much money you earn in the game. In detail, you should consider there are 14 opponents on the server who has very different strategy in the game. you will play 10000 games with each player. and your score is the average score you got from each opponent.
there's one trivial solution, you can provide some human-knowledge in your program. such as when your card is very good, then you will bet with server, otherwise you will give up in the game. however with some fixed human-knowlege, you can't win the game because you're never more clever than computer:)
another solution is using ML which is a very suitable algorithm to make your program learn to gamble in the game itself. in such situation, no matter how your opponent change you will learn to win.
So, i used a classical unsupervised learning algorithm called Reinforcement Learning(RL) to learn to gamble. Now i will share the result with you:

1. I use Q-learning algorithm
2. Q-learning is quite largely based on statistics. in fact RL is calculating the maths expecation of the money you can win under a specific strategy you play in a specific state. For example, you get two "Queen"s in the game, RL will calculate under this situation, if you bet, how much you will win on average, or if you give up, how much you will lose on average. In this way, RL will tell you the best strategy under a specific state. if you are familiar with Markov process, you will under stand Q-learning easily.

Till now, you will think that RL is really a very good learner who can always win the game. however in reality, i met lots of prolems, and now i will share it with you and give you my explanation:

1. Very slow converge. since there's so many states, and the next state is undefinite. the convergence is very slow. Since you're only allowed to play with your opponent for only 10000 rounds, you can't learn almost any thing.

2. then i tried another approach, I eliminate lots of states, and construct a relatively very small model of the game. however, i lose again. At last, i found that is because the model is too small, in such a model, the game is quite unfair, the result of RL learning told me that in lots of situation no matter what strategy you play, you will lose.

At last, i don't use RL learning.

Google CV filtering algorithm

The following algorithm is used by google to filter many CVs of applicants.
void filter(CV)
{
if(CV.university.contains("US")
or CV.university.contains("Tsinghua")
or CV.university.contains("Peking U"))
{
accept(CV);
}
else
reject(CV);

}

funny tutorial on C pointers

求解多数数问题。

问题描述：A[1..n]是n个整数，现要求找出多数数。多数数就是出现的次数大于[n/2]的数。例如1,2,3,3,3,3,4。由于3出现4次大于[7/2]，所以3是多数数。求一个复杂度O(n)的算法求出多数数。

解答：这个问题看似简单，因为O(n^2)复杂度的算法是很容易得到的，只需统计每个数出现的次数和[N/2]比较就可以了。但是现在要求O(n)复杂的算法就需要对问题更深入的理解了。

方法一：中位数法，一个序列的中位数就是将这个序列排序后，中间的那个数。比如说：3,1,2,4,5排序后就是1,2,3,4,5。那么中位数就是位于中间的3。那么中位数和多数数有什么关系呢？很简单，如果多数数存在的话，中位数一定就是多数数（这个自己去想为什么）。中位数通常是使用类似于Quick sort的方法来求解，平均复杂度O(nlgn)。但是有一种很复杂的经典方法是的中位数在O(n)可解。参考MIT的《算法导论》。
那么有些人可能要问了，万一多数数不存在怎么办呢？这个时候中位数就不是多数数了，因为多数数压根就不存在。但是这个问题很好解决!那就是对求出的中位数做一次check，看看他是不是多数数就可以了。check的过程是O(n)复杂度，所以总复杂度是O(n).

方法二：这种方法比较巧妙。我把它叫做多数数统计法。算法如下：
(1) num = A[1]; (假设多数数就是A[1])
(2) freq = 1; (多数数目前的出现次数为1)
(3) for(i = 2; i <= n; ++i)
{
if(A[i] == num)
++freq;
else
{
--freq;
if(freq == 0)
{
num = A[i];
freq = 1;
}
}
}

(4) 如果多数数存在，算法结束时，num就是多数数。若多数数不存在，如果你读了方法一，你应该知道怎么做了。

方法三：消去法。其实这种方法和方法二差不多，只是这种方法更容易读懂。
从A中寻找Ai，Aj使得Ai != Aj，此时将Ai和Aj从A中去除，不停得去掉A中的数，直到A中所有数都相等，则若多数数存在，该剩下的数是多数数。
简单证明一下:
设u表示多数数在A中出现的次数，v表示非多数数在A中出现的次数(v = n - u)。
那么上述从A中去除两个数的操作，使得对新的集合A'有两种情况：
对A'
(1)两个数都不是多数数，则v' = v - 2;
(2)两个数中有一个是多数数，则v'= v -1; u' = u - 1;
若多叔叔存在，u > v. 所以当消去操作无法进行的时候，即A中所有的数都相等的时候，v = 0, u>0因此A中剩下的数一定都是多数数了。

至此，该问题得到了圆满的解决，看完了别忘了点广告哦！

神奇的数学，神奇的lamda演算

今天读了一篇〈康托尔、哥德尔、图灵——永恒的金色对角线〉（刘未鹏）(博客资源中可以下载），感慨颇深。机缘巧合之下读到这篇文章，读了第一段我就入迷，不得不继续下去，于是我花了一晚上读完了这篇12页的文章。一部精美的数学史展现在我的眼前，原来在计算机的背后竟有这么美妙的数学理论。
截取该文前言，有兴趣的人可以搜索这篇文章读完。

哥德尔的不完备性定理震撼了20世纪数学界的天空，其数学意义颠覆了希尔伯特的形式化数学的宏伟计划，其哲学意义直到21世 纪的今天仍然不断被延伸到各个自然学科，深刻影响着人们的思维。图灵为了解决希尔伯特著名的第十问题而提出有效计算模型，进而作出了可计算理论和现代计算 机的奠基性工作，著名的停机问题给出了机械计算模型的能力极限，其深刻的意义和漂亮的证明使它成为可计算理论中的标志性定理之一。丘齐，跟图灵同时代的天 才，则从另一个抽象角度提出了lambda算子的思想，与图灵机抽象的倾向于硬件性不同，丘齐的lambda算子理论是从数学的角度进行抽象，不关心运算的机械过程而只关心运算的抽象性质，只用最简洁的几条公理便建立起了与图灵机完全等价的计算模型，其体现出来的数学抽象美开出了函数式编程语言这朵奇葩，Lisp、Scheme、Haskell… 这些以抽象性和简洁美为特点的语言至今仍然活跃在计算机科学界，虽然由于其本质上源于lambda算子理论的抽象方式不符合人的思维习惯从而注定无法成为主流的编程语言，然而这仍然无法妨碍它们成为编程理论乃至计算机学科的最佳教本。而诞生于函数式编程语言的神奇的Y combinator至今仍然让人们陷入深沉的震撼和反思当中…

然而，这一切的一切，看似不很相关又有点相关，认真思考其关系却又有点一头雾水的背后，其实隐隐藏着一条线，这条线把它们从本质上串到了一起，而顺着时光的河流逆流而上，我们将会看到，这条线的尽头，不是别人，正是只手拨开被不严密性问题困扰的19世纪数学界阴沉天空的天才数学家康托尔，康托尔创造性地将一一对应和对角线方法运用到无穷集合理论的建立当中，这个被希尔伯特称为“谁也无法将我们从康托尔为我们创造的乐园中驱逐出去”、被罗素称为“19世纪最伟大的智者之一”的人，他在集合论方面的工作终于驱散了不严密性问题带来的阴霾，仿佛一道金色的阳光刺破乌云，19世 纪的数学终于看到了真正严格化的曙光，数学终于得以站在了前所未有的坚固的基础之上；集合论至今仍是数学里最基础和最重要的理论之一。而康托尔当初在研究 无穷集合时最具天才的方法之一——对角线方法——则带来了极其深远的影响，其纯粹而直指事物本质的思想如洪钟大吕般响彻数学和哲学的每一个角落[1]。随着本文的展开，你将会看到，刚才提到的一切，歌德尔的不完备性定理，图灵的停机问题，lambda算子理论中神奇的Y combinator、乃至著名的罗素悖论、理发师悖论等等，其实都源自这个简洁、纯粹而同时又是最优美的数学方法，反过来说，从康托尔的对角线方法出发，我们可以轻而易举地推导出哥德尔的不完备性方法，而又后者又可以轻易导出停机问题和Y combinator，实际上，我们将会看到，后两者也可以直接由康托尔的对角线方法导出。尤其是Y combinator， 这个形式上绕来绕去，本质上捉摸不透，效果上神秘莫测的算子，其实只是一个非常自然而然的推论，如果从哥德尔的不完备性定理出发，它甚至比停机问题还要来 得直接简单。总之，你将会看到这些看似深奥的理论是如何由一个至为简单而又至为深刻的数学方法得出的，你将会看到最纯粹的数学美。

接着该文顺序介绍了图灵停机问题（完美的证明了不存在一个算法可以判定给定的程序和给定的输入条件下是否能够停机），lamda演算基础（lamda演算其精妙看了真的让人感叹！再加上Y combinator，这个仅有2个公理的公理系统竟然和图灵机等价，也就是具有图灵机同等的计算能力，这也是我们当今计算机的计算模型），Y cominator，歌德尔不完备性定理，康托尔对角线方法。佩服佩服！
太完美了，不敢相信居然还有这样的理论。而歌德尔不完备性证明竟然只是他的博士论文。真不知道这些伟大的思维是怎么诞生地，真不知道他们为何可以有这样不同寻常的想象力。我实在太佩服了，我开始相信哲学了，也许哲学真的是一切学问的学问，也许他真的就是所谓的metaphysics.
引用康托尔的一句话“我看到了它，却不敢相信它”
学了这么久计算机，我觉得我越来越不懂计算机这个东西了。

Google Adsense全攻略。

Google Adsense是一个广告合作项目。作为网站发布商的你可以通过Adsense获取利润。Adsense提供三种方式获得利润：
1. 如右侧Google搜索条：若访问该博客的同志通过该搜索条进行搜索并点击了搜索结果中被Google标示出的广告链接，那么我将获得小额利润。
2. 右侧搜索条下方是一个Google推广Adsense的图标，如果访问该博客的朋友通过阅读此文也希望在自己的博客上添加Adsense广告，那么可以点击该图标并加入Adsense，这样我也可以获得小额利润。
3. 那就是右侧Google提供的广告，通过在网页中插入一段javascript代码，如果可爱的你为了支持我的博客建设，那就点击吧！

好了，别的不多说，看过文章别忘了点广告哦。。。

千里之行，始于足下

终于在blogger开通了我的博客，希望和大家分享我在计算机学习过程中遇到的问题和经验。大家要多支持我！谢谢。