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