使用的就是mitchell的那本ML中关于naive bayesian classifier讲解用到的
数据。20个邮件组的邮件，共约20000条记录。
主要是实践了下naive bayesian classifier。做了两个集合的实验，包括全集和书中实践的小集合（3个特定的邮件组集合）。
全集上最后的准确率可以达到83.7%。而使用小集合对比书中的（89%-90.5%），可以达到91.3%的准确率。
其中有一些需要注意的：
1. 对低频概率的光滑操作很重要。主要用于计算P(w|g)时在w频次很低的情况下。
如果没有光滑，答案整个就被误差毁了，直接准确率掉到20%以下。
如果使用P(w|g)=(C(g,w)+1)/(C(g,all_w)+C(words_in_g))可以保证结果达到预期水平
如果使用P(w|g)=(C(g,w)+1)/(C(g,all_w)+C(words))结果还更好些。这似乎和预期不是很符合。
2. 对stopword的选取。
使用idf作为选择标准（不取log）。刚开始选定的覆盖文章范围在0.6才去除。后来发现一直到1/12都能保证单调递增。效果不错。
3. 既然bayesian是逆概，还尝试了正向概率计算求答案，也是使之相互独立。准确率在75%左右。怀疑是模型本身并不是reasonable的。（就是比naive bayesian还不靠谱）
从误分类的数据来看，有些确实是无法很好分类。同时后续改进还有这么一些方法：
1. 低频词的影响。
2. 调整模型，使之更好去识别。这在看论文。看看是否可行。
同时今天还看了一篇介绍bayesian的一些应用之处的
文章。讲的很广泛，把很多知识都串一起了。很好！
Finding the k shortest paths,
D Eppstein
这篇论文不错。方法很好，但是我觉得读的有点拗口。
说几个重点nb的吧。
1. 能够将路径用最短路径树和“弯路”表示
2. 考虑到路径的层次结构。
如果考虑到以上两点会有很多启发的，之后还有几个nb的：
3. 把堆表示在dag上。
4. 这个最最nb,很容易考虑到每次找到一个最小后缀，然后更新堆，但这样复杂度就是nm的。而其通过将每个点的后缀重新组织成一个小堆。就控制住复杂度了！
这篇论文之前比赛的时候就很想看，后来搞输入法的时候又听说了，还是没时间看。今天花了一下午看了还是挺开心的。不过觉得他有的地方方法有些冗余或者说不是很优，什么时候再细细想想。今天好困。。。
最大概率分词问题及其解法，hit的刘挺等，1998
这篇文章前面给出的一些模型对我这个新手来说不错。后面对问题的解决一般。
第一个问题是找分割点，这个很简单，在找到每个点的最远距离后，O(n)扫一遍就可以了。
第二个问题是每个字段内的最优概率计算。这个如果按原有的概率算比较难，n-gram的n不确定，不过他这里用的是unigram
这样就简单多了。。取log以后最短路，dp啥的爱咋搞咋搞。
最终结果是金牌，但没有进入Final。还是能接受的结果，但毕竟还有进步的余地，希望下次能再好点。
题目难度一般，不过阅读和题量比较大，所以还是挺郁闷的。我当时基本都在敲代码没多少需要想的题。。
还是要多多练习啊。
PS.火车上听说bamboo他们硬敲了D题。。700多行代码无模板。。Orz。。
最近其实看了很多相关的内容，比如Petr在某次TCHS前在房间里面和别人聊天的内容啊，之前自己也想过有时候自己太勉强自己了，应该在需要休息的时候放松啊。今天又觉得，其实像现在如果比较不在状态的时候，可以尝试去看看以前的笔记啊，写点总结啊啥的。都挺好的。总之要自我调节，不可太急躁。
这篇日志作为一篇开放式的吧，我想到啥就过来加点，作为自己的一个小Tips。
- 我需要静一静，写代码是一项需要安静的工作，做自己的就应该少说话。[2008年10月4日13:27:40]
- 昨天做一个问题一直在网上搜索没有好的答案。但后来和小亮交流下回去自己静静想想就会了，其实并不复杂，但自己没有静下来好好想想才导致自己半天没弄出来。
还差一道题，先publish下这个beta版的，第一次用CTex写的，呵呵。
总的来说这套题还是比较简单的，数据也不强，不过也都要想想。
http://www.cppblog.com/Files/NickGu/nwerc2003.pdf题目列表：
欢迎下载，如果谁会做最后一道麻烦给我留言。。有什么问题可以给我留言也可以电邮我。