我的黄金时代

把事情做好

Dan — Sat, 25 Oct 2008 19:23:35 +0800

这几个月都在比较专注的做一个题目，几个月过后，一个听上去很可行的模型在实验中被验证无效。

回想当初刚拿到这个题目的时候，顿时被题目美好的目标吸引住了。经过初步的调研，我得到了一个错误的直觉，把一个原本很难、广度也相对比较小的题目，当作了一个很少人做的简单而且新颖的题目。然后就开始想尽办法开始炮制自己的模型。经过“不懈努力”终于得到了一个听上去很美的模型和若干华丽的特征。怀着对美好的憧憬，带着要发牛paper的动力，就开始“噼里啪啦”的做一个不小的实验。

最终，就有了开头提到的结果。

其实在以前和astroguo师兄讨论的时候，他就提到了这个题目的困难性。而我却打肿脸充胖子的做一些无力的argue。原本就经验不足，再加上求“功”心切，怀着对牛会paper的渴望，抱着一个有些牵强的模型，撞到了墙，虽然又努了努力，想绕过去，却发现其实是个死胡同。

即使对我这样“一无所有”的家伙，发paper也不应该成为做研究的指挥棒。
静下心来，纯真一些。
最后再引用QQ师兄的一句话：

把事情做好。

做研究就像挖坑

Dan — Tue, 21 Oct 2008 17:20:47 +0800

前天晚上在水房洗衣服时和一个朋友聊天，聊到了做研究。
其间谈到了实验失败的共同感受。
朋友做了这样一个比喻：

做研究就像挖坑，
有大牛，眼光敏锐，瞅准了地方，在一个地方挖了个坑，挖到了水，然后拿个桶打上水，到别的地方去灌水；然后众小牛们也都跟着跳进了大牛挖的坑，继续挖坑，打水，灌水，坑越来越深，水越来越少。
毫无疑问，这些牛们是幸福的。
如果不幸挖到了石头，就只能把土添回去，然后踩平，再然后拍拍手上的灰，也没有人知道你曾充满热情并努力的挖过这个坑。

问答那些事儿

Dan — Sat, 06 Sep 2008 14:56:07 +0800

一个即将进入问答方向的师弟问我有什么问答方向的论文推荐给他看，记得自己刚进入这个领域时也有着很多类似的困惑，虽然只有一年的短浅经历，但我斗胆写下下面的文字，希望这些文字对他以及和我们有着同样困惑的初学者有所帮助。以下的文字不是说教，只是一些经历和思考的片段。

在IR、NLP领域中，现在的一般看法，大家都把QA归类为信息检索中的一个Open Problem。因为目前的检索系统都是通过输入一堆关键词，然后系统返回一堆候选结果，而人们更期望于用人类的自然语言提问，来得到一个精确的答案。可能这里的QA任务的来由与AI中的QA系统定义有所区别，但我想算是异曲同工。

为了完成以上终极目标，或者说为了得到更好的检索效果，人们开始研究NLP技术来帮助改进检索。自然语言处理技术主要分为两大流派，一种是基于规则的方法，即人根据自己的先验知识来手工制定规则；另一种是基于统计的方法，即在大规模的语言现象中，利用机器，自动的统计其中的潜在的规律。基于规则的方法缺点显而易见，需要大量的专家利用大量的人力时间来制定规则，规则也不一定是完备或者正确的，也因为自然语言本身就非常灵活。基于统计的自然语言处理方法随着近些年统计机器学习的发展，而逐渐占据了主流。

其中，概率与统计、线性代数等构成了统计机器学习的基础。
另外，统计机器学习中一大类问题是讨论模式分类。综上，我们可以得到下面的一幅图。无箭头的边代表包含关系，有箭头的边代表支持关系。

关于自然语言处理、统计机器学习和概率三者的关系存在着这样一个笑话式的说法：三流的统计学家做机器学习，三流的机器学习专家做自然语言处理。我也时常在反思并与前辈、同僚们进行讨论，我们所从事的事情，是否只是因为工业界经济效益的带动，而形成的一个华丽的坑。我们在做这样的应用研究时，总是会存在这样一个“模式”，拿到某个问题，然后对其进行观察、分析，建立模型，而这个模型的理论、求解等通常都已经是机器学习专家、数学家为我们解决了的。因此我们不免会担心，离这些基础远了，我们所做的事情是否只是高劳动力低价值、低影响力的，是否只有去做那些基础科学能产生很大影响力的学问才算做是有价值的呢，甚至我们所做的事情是否属于伪科学。然而以我目前浅薄的眼光来看，应用研究，观察与抽象出事物的本质是最关键的，我更愿意把它称作为一门实验科学。我觉得以上疑问可以在与物理对人类进步的推动、数学和物理的关系进行类比来得到一个答案。信息检索、自然语言处理不就正在改变人们的生活么？随着基础设施的完善，也许我们会距离终极目标越来越近。

QA是一个异常困难、庞大的题目，因此人们尝试开始从各个方面来攻克它。以TREC为例，在TREC的QA main Task中，有Factorid QA、List QA、Definitional QA三种相对来讲比较简单的subtask。然而这三种QA所覆盖的范围也远小于实际中的QA所包含的各种形式。起初我在知道自己以后要做QA的时候，感觉到有些诚惶诚恐，认为这几乎就是一个美丽的泥潭，寸步难行。但是进入这个领域一年以后，我又有了不同的看法。我认为QA，在现有的条件下，可以多做一些tractable的工作。跟踪一下近几年IR/NLP related top conferences中有关QA的论文，我们不难发现，一些新的贴近应用的QA任务被提出，其中不少都是extraction problem。碰巧的是我最近做的两个工作也都是extraction based method。似乎，这样看来这类QA多了些Data Mining的味道，呵呵。

因为QA任务本身的特点，导致有关QA的论文，关于各种问题的，很多、很杂。所以，如果没有什么目的性的看QA论文，就犹如同大海捞针。因此，我认为可以不用太着急看QA的论文，不妨先打好上面说的那些基础。有了比较明确的题目后，再来有针对性的阅读论文。当然，这不是一个规定好的顺序，我们也不可能总是以这样一个理想的方式去学习、做研究。book driven、task drivern、paper driven，我们更多的是在这样一个混合的滚雪球的方式中沉淀、成长。

最后，我推荐个书单吧（前两本我也没看过，从Dahua Lin的blog里看来的推荐，打算最近开始读）:
[Gilbert Strang] Introduction to Linear Algebra (3rd Ed.)

[V.N.Vapnik] The Nature of Statistical Learning Theory
统计学习理论的本质

[Duda et al] Pattern Classification (2nd Ed.)
模式分类

[Mitchell] Machine Learning
机器学习

[D.Manning et al] An Introduction to Information Retrieval

[D.Manning et al] Foundations of Statistical Natural Language Processing
统计自然语言处理基础

[J.Han et al] Data Mining Concepts and Techniques (2nd Ed.)
数据挖掘概念与技术

还有一篇众牛合写的QA survey：
[John Burger et al] Issues, Tasks and Program Structures to Roadmap Research in Question & Answering (Q&A)

1/11

Dan — Tue, 22 Jul 2008 02:01:31 +0800

背起行囊，踏遍南北。

今天，我为自己许下一个愿望。

为什么呢？

Dan — Tue, 08 Jul 2008 19:46:01 +0800

因为，我热爱我的事业，

同样，我也热爱我的生活。

无题

Dan — Sat, 07 Jun 2008 16:37:26 +0800

又生病了，躺在床上，想的事情自然也就多起来。

这一年多的时间，有收获，也有很多遗憾。

可能是自己一直以来的习惯，亦或者是性格使然，使得自己太过专注于一件事情，疯狂的压榨着自己。虽然败的一塌糊涂，但没有关系，因为对的起自己。已经平静了许多，至少回过头来，这仍然是一份经历。

“人要有勇气去改变那些能够改变的事情，有涵养去接受那些不能改变的事情，有智慧去区分哪些是能够改变的、哪些是不能改变的。”

这其中，自己也犯下了错误，当生活单调到没有任何色彩，我想这已经不是好的生活了。
其实我应该可以做更多更有意义的事情。

一直以来，我以为，我最大的幸运就是，总是能跟着自己的意愿和兴趣而走，但却没有意识到事实上缺少了一个长期的规划。
第一次变得这么优柔寡断。
虽然做决定的时候，我是会犹豫的，因为我总是希望找出一个最大的成功概率。
但是决定做了，我是不会后悔的。

做决定，做选择之前，甚至做事情之前，我总喜欢给自己扣上一座山，其实又何必总给自己这么大的压力呢。
记得我以前在开导别人时，总会说：
“现在回头想想你许久以前遇到的困难，哪一个不是微微一笑就过去的呢？”
所以不要总给自己背上太多的包袱，因为我们还年轻。
我们不应抱着游戏的态度而人生，但人生却是场游戏，我们应该学会去体验和享受其中。

最近又把喜剧之王翻出来看了一遍。
不论是跑龙套的，还是主角，我都热爱我的这份事业，更重要的是，这是我自己的生活。

“其实，我是一个胖子。”

囧

Dan — Sun, 20 Apr 2008 19:09:53 +0800

哈尔滨创下了47年来的同期最高气温。
昨晚回到寝室后，
有些口渴，
于是乎去公寓楼下的小卖铺，
购得一支冰棍，红豆沙的。
拿到楼上后方才看到生产日期是去年夏天，
不过保质期18个月，还能吃。

拆开包装，
……
结果嘴唇被粘在了冰棍上（可能是冷冻太久的缘故吧-_-），
忍着阵痛，将嘴唇与冰棍分离开来。
发现嘴唇上流出的血已经在冰棍上留下了很大的印记。

寝室兄弟看到冰棍上有红印，
惊呼：“我靠，你这冰棍还盖红章子呢！”

纪念那些只能绽放一日的桃花，
特改诗一首：

昨日今时此路上，
人面桃花相映红。
桃花不知何处去，
人面依旧笑春风。

TSP/Bitonic Tour

Dan — Sat, 29 Mar 2008 21:21:56 +0800

poj 2817 WordStack

先枚举预处理每两个单词之间的最大值。
然后易看出是要寻找一条遍历所有顶点一遍的最长路径，也即找到一条最长的Hamilton Path。(TSP问题)

状态为d[state][last]，代表遍历了state这些点，并且最后一个点为last时，最长的Hamilton Path。
状态方程为：d[state][last] = d[state-(1<<i)][i] + w[i][last] ( (i!=last) && ((1<<i)&state) )

poj 2677 Tour

TSP问题简化版，又称为bitonic tour。（参见算法导论习题15-1）

不妨将问题看作两个人同时从左向右走，并且两个人走过所有的点，且两人走过的点均不同，求两人走过的路径之和最短解。
状态为d[i][j]，代表了第一个人走到点i，第二个人走到点j，并且i>j，且i之前（包括i）的所有点均被走过，最短路径和。
状态方程为：
(1) i==j+1，d[i][j] = d[j][k] + w[k][i] ( 0<=k<j )
(2) i>j+1，d[i][j] = d[i-1][j] + w[i-1][i]

我想…

Dan — Fri, 28 Mar 2008 21:10:44 +0800

我想换一个两边都能出声的耳麦…

我想换双不漏风而且不漏雨的鞋子…

我想每天早上都有早饭吃…

我想把想读的书读完…

我想尽情的做有意义的research…

我还想更新blog，就像现在一样….

我想，我该去做些有意义的事情了…

“有意义的事就是好好活；好好活就是做很多很多有意义的事”

n个有序集合的并与交

Dan — Fri, 28 Mar 2008 20:06:04 +0800

(1) n个有序集合求并
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组归并，得到一个有序数组。

解法[1]：
当n=2时，显然，我们只要线性扫描两个数组即可，复杂度O(size(arr[0]) + size(arr[1]))；
当n>2时，我们可以使用上述方法对有序数组两个两个的进行归并，最终得到一个有序数组。在总的归并过程中，每个元素被操作O(logn)次，因此，总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

解法[2]：
不妨假设有序数组是按照非降序排序的。归并时，使用最小堆。首先将n个数组中的首元素压入最小堆。每次弹出最小堆中的堆顶元素，相当于得到了n个数组中当前处理位置中最小的元素，然后将弹出元素所在数组中的下一个元素压入最小堆。每个元素在最小堆上均被插入和弹出一次，O(logn)，所以总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

(2) n个有序集合求交
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组求交，得到一个有序数组。

解法：
对所有数组线性扫描一遍即可。不妨设有序数组是按照非降序排序的。
设min为所有数组当前被扫描位置的最小值，max为最大。若min==max，则将此值加入新数组。若min!=max，则对每个数组从当前位置起扫描，直至找到第一个大于等于min的数，如此循环。
时间复杂度为，O(m)，m = sum(size(arr[i]))， 0<=i<n。

伪码如下：

	for each arr
		pos[i] = -1

	min = max = 0
	end = false
	while end == false
		if min == max
			for each arr
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
		else if min != max
			min = max
			for each arr
			while arr[i][pos[i]] < min
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
			if arr[i][pos[i]] > max
				max = arr[i][pos[i]]
		while end == false
			if min == max
			newarr.add(min)