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