使用的就是mitchell的那本ML中關(guān)于naive bayesian classifier講解用到的
數(shù)據(jù)。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))可以保證結(jié)果達到預期水平
如果使用P(w|g)=(C(g,w)+1)/(C(g,all_w)+C(words))結(jié)果還更好些。這似乎和預期不是很符合。
2. 對stopword的選取。
使用idf作為選擇標準（不取log）。剛開始選定的覆蓋文章范圍在0.6才去除。后來發(fā)現(xiàn)一直到1/12都能保證單調(diào)遞增。效果不錯。
3. 既然bayesian是逆概，還嘗試了正向概率計算求答案，也是使之相互獨立。準確率在75%左右。懷疑是模型本身并不是reasonable的。（就是比naive bayesian還不靠譜）
從誤分類的數(shù)據(jù)來看，有些確實是無法很好分類。同時后續(xù)改進還有這么一些方法：
1. 低頻詞的影響。
2. 調(diào)整模型，使之更好去識別。這在看論文。看看是否可行。
同時今天還看了一篇介紹bayesian的一些應用之處的
文章。講的很廣泛，把很多知識都串一起了。很好！
Finding the k shortest paths,
D Eppstein
這篇論文不錯。方法很好，但是我覺得讀的有點拗口。
說幾個重點nb的吧。
1. 能夠?qū)⒙窂接米疃搪窂綐浜?#8220;彎路”表示
2. 考慮到路徑的層次結(jié)構(gòu)。
如果考慮到以上兩點會有很多啟發(fā)的，之后還有幾個nb的：
3. 把堆表示在dag上。
4. 這個最最nb,很容易考慮到每次找到一個最小后綴，然后更新堆，但這樣復雜度就是nm的。而其通過將每個點的后綴重新組織成一個小堆。就控制住復雜度了！
這篇論文之前比賽的時候就很想看，后來搞輸入法的時候又聽說了，還是沒時間看。今天花了一下午看了還是挺開心的。不過覺得他有的地方方法有些冗余或者說不是很優(yōu)，什么時候再細細想想。今天好困。。。
最大概率分詞問題及其解法，hit的劉挺等，1998
這篇文章前面給出的一些模型對我這個新手來說不錯。后面對問題的解決一般。
第一個問題是找分割點，這個很簡單，在找到每個點的最遠距離后，O(n)掃一遍就可以了。
第二個問題是每個字段內(nèi)的最優(yōu)概率計算。這個如果按原有的概率算比較難，n-gram的n不確定，不過他這里用的是unigram
這樣就簡單多了。。取log以后最短路，dp啥的愛咋搞咋搞。
最終結(jié)果是金牌，但沒有進入Final。還是能接受的結(jié)果，但畢竟還有進步的余地，希望下次能再好點。
題目難度一般，不過閱讀和題量比較大，所以還是挺郁悶的。我當時基本都在敲代碼沒多少需要想的題。。
還是要多多練習啊。
PS.火車上聽說bamboo他們硬敲了D題。。700多行代碼無模板。。Orz。。
最近其實看了很多相關(guān)的內(nèi)容，比如Petr在某次TCHS前在房間里面和別人聊天的內(nèi)容啊，之前自己也想過有時候自己太勉強自己了，應該在需要休息的時候放松啊。今天又覺得，其實像現(xiàn)在如果比較不在狀態(tài)的時候，可以嘗試去看看以前的筆記啊，寫點總結(jié)啊啥的。都挺好的。總之要自我調(diào)節(jié)，不可太急躁。
這篇日志作為一篇開放式的吧，我想到啥就過來加點，作為自己的一個小Tips。
- 我需要靜一靜，寫代碼是一項需要安靜的工作，做自己的就應該少說話。[2008年10月4日13:27:40]
- 昨天做一個問題一直在網(wǎng)上搜索沒有好的答案。但后來和小亮交流下回去自己靜靜想想就會了，其實并不復雜，但自己沒有靜下來好好想想才導致自己半天沒弄出來。
還差一道題，先publish下這個beta版的，第一次用CTex寫的，呵呵。
總的來說這套題還是比較簡單的，數(shù)據(jù)也不強，不過也都要想想。
http://m.shnenglu.com/Files/NickGu/nwerc2003.pdf題目列表：
歡迎下載，如果誰會做最后一道麻煩給我留言。。有什么問題可以給我留言也可以電郵我。