2007年8月29日 星期三

Hidden Markov Model

最近被迫得讀 Hidden Markov Model (HMM) 相關的內容,我入門的方法是參考下面這三篇:

最近學新東西,愈來愈習慣先看完WikiPedia的介紹再開始,WikiPedia上的介紹通常比書裡寫得還要清楚,真方便。

個人認為最好理解HMM的例子是語音辨識,摘錄Viterbi algorithm裡的一段例子:

For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the “hidden cause” of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

每個文字代表一個state,state和state之間有條件機率,稱為state transition,即文字的連續關連性,比方「駱」下個字出現「駝」的機率很高,出現「馬」的機率很低,丟個文章集統計一下就可以得知state transition。主要的差別是這裡假設每個state只會被上個state影響,所以不會直接統計「王八」下個字出現的機率,得先算出「王」到「八」才行。這點和 N-gram 的做法不同,以文字為例子的話,可以將state transition看成是 2-gram 而已。

單純文字之間的關聯已有很多發展空間,比方套用 Markov chain ,算出給定第一個字的情況,第五個字最有可能出現什麼字?或是無論開頭為何,第三個字最有可能出現什麼字?而在語音辨識的例子裡,除了 state (=文字)外,還有 symbol 。

每個 state 會產生一個 symbol ,打個比方,可以想成在數位電路裡的 Finite State Machine 中的 Moore Machine ,跟著一連串的 state 轉換,每個 state 都有伴隨輸出的資訊,但在 HMM 裡,每個 state 不會只輸出一種 symbol ,而是各個 symbol 有對應的輸出機率,所以不只 state 和 state 之間有條件機率, state 和 symbol 之間也有條件機率。在語音辨識的例子裡, symbol 是聲音訊號。畫圖太麻煩了,麻煩各位發揮想像力, HMM 的架構可看成兩層,上層是一個 graph , vertex 表示 state, edge 表示 state 間的條件機率;下層是數排 vertices 每個上層的 vertex 對應到下層一排 vertices ,之間有個有向邊由上層指向下層, edge一樣是條件機率,表示在這個 state 下,會產生的 symbol 機率為何。

那麼 HMM 要解決的問題為何呢?直接從語音辨識來看比較容易理解,我們可以取得一連串的聲音訊號,經過處理後斷成一個個文字的聲音,但我們不知道每個聲音對應到的文字為何?考慮這個例子(喔,注音文的正當使用):

ㄌㄨㄛˋ ㄊㄨㄛˊ ㄏㄨㄟˋ ㄈㄟ

這個例子對應的文字可能是「落鴕會妃」,也可能是「駱駝會飛」,那一個組合較合理,得看文字間的接連出現的機率夠不夠高。在 Markov chain 的例子裡,我們是直接由 state 找出 state sequence,而HMM的例子裡,我們不知道 state 為何,所以稱為 Hidden State ,我們必須由 observation ( symbol sequence ) 來推測原來最有可能的 state sequence。

注意上述的說明都是假設 model 是正確的, model = initial state probability + state transition probability + symbol probability (emission probability)。在 Machine Learning 裡有些方法說明如何找出最有可能的 model ,有空再來看看吧。

2007年8月26日 星期日

前進的理由?

看到bc的文章有感,留了這麼一段話:

隨著不斷前進, 也會發現許多過去的同伴停下腳步,
安於在某個階段, 覺得有點可惜
 
有時我也會想停下來, 反正活得快樂就好, 有沒有大發展到是其次,
只是呢, 偶而又會想著, 如果就這麼停下來, 似乎太可惜了,
好像會對不起過去的自己, 白費他們的辛勞, 而湧出繼續往前踏的鬥志
 
愈接近碩士畢業, 這種想法愈強烈,
若最後我決定出國念博士的話, 大概是因為不想停止發展吧

bc在blog上提到數年後回頭來看,還是心情文最有感覺吧,我也這麼認為,偶而多寫些心情文吧。技術文則是留給自己備查以及分享給大家用的。

2004 - DMCC Work 3

聽膩了最近放的音樂,太累睡不著又無法思考,想說找點平常很少聽的風格來放好了。忽然想到這張DMCC Work 3 (絕版了哦!),拿出來放感覺真不賴,大學生涯裡值得紀念的一個作品,雖然大二因此更忙了不少,但不管是當時還是現在,都認為是相當值得的事。詳細介紹見這裡

這張CD裡的一些作者還有持續在創作,像是ychm,可以從他的blog聽到他的作品。還有Katsu的作品也有部份試聽放在個人工作室網站上。印象中社站上應該有一些作品可以試聽,不過社站目前似乎掛站中。後來的學弟妹們也相當厲害,遜腳的我在做完最後一首soar時面臨瓶頸,得花不少心力才能突破,於是就停擺了,只有偶而練練琴。

不知道何時才能痛下決心加強樂理重新嘗試作曲。

ps

雖然Blog自動偵測的Related Post很少準過,但這篇的Related Post也差太多了吧。

2007年8月24日 星期五

鳥之詩各種編曲版

整理一下鳥之詩的曲子,這首曲子有太多版本了,這裡列出幾個很有特色的曲子,其實只是老梗重新整理而已。

原版

=AIR=鳥之詩 MTV。應該是原版吧。

Re-feel版

http://key.soundslabel.com/discography.htm,進去後搜”Re-feel”,有片段試聽。最近練完Re-feel的《夏影》後,終於要開始練這首了。

另一個鋼琴版

spearmint介紹的,AIR動漫中,史上最完美的鳥之詩。網頁下方有譜可以下載,這版也很棒,看看半年內能不能練起來吧。《夏影》練了21天,推測Re-feel的《鳥之詩》要練20~30天,這首鐵定要更久。

以結尾來說,我最喜歡這版的,倒數第二頁時將原版的前奏和主弦律結合起來,並在最後一頁將氣氛托到另一個高潮。中間刻意改變melody聽起來也很耳目一新(第二頁中間),聽習慣Re-feel後改聽這首感覺很棒。

炫技版

primenotes - 『ピアノソナタ第2番 第一楽章 -鳥の詩-』 (VisualArt’s/Key AIRより)。我覺得弦律不錯,但難度太高,無法將曲子彈得正確又融入感覺。當時從herbage那看到時,在這篇有一些討論。

Rock版

herbage介紹的,X+鳥の詩(vocal:ゼブラ) 「METAL of 鳥の詩 -AIR-」。嗯...眼見不一定為憑啊。

2007年8月23日 星期四

試用JRuby失敗,只好用Java讀圖檔

Ruby查不到怎麼讀圖檔,只好從Java下手,原本想用jruby來搞定的,結果碰上jruby的bug,jruby還未成為完全體嗎?Java的解法見這裡,寫好的code在這裡。以下是用jruby的測試情況:

# jruby -v ruby 1.8.5 (2007-06-07 rev 3841) [amd64-jruby1.0] # cat read_bmp.rb include Java import java.awt.image.BufferedImage; import javax.imageio.ImageIO; f = File.new("test.bmp"); img = ImageIO.read(f) # jruby read_bmp.rb RubyFile(test.bmp, 0, 3) :-1: no read with arguments matching [class org.jruby.RubyFile] on object JavaUtilities (NameError)

ImageIO.read()無法讀出BufferedImage,只好重操老本行寫Java,輸出的method打成puts…,幸好Java的compiler很強,就算很久沒寫Java,想寫出能動的code還是很快,大不了多compile幾次罷了。

2007年8月22日 星期三

Introduction to Data Mining

書藉基本資料: Introduction to Data Mining

最近在做clustering的研究,仔細讀了這本書的ch8, 9,愈讀愈覺得該學的東西愈多,作者們真是太強大了,怎麼能懂這麼多東西,又能這麼有條理地分析整理出來,並配合許多直接易懂的例子說明。如果有時間的話,真想把這本書好好地讀一遍,但真的要讀完一遍,半年的時間都不夠吧,特別是需要數學較深的方法不是三兩下就能體會的。

讀的過程裡,漸漸產生懷疑,目前做clustering相關研究的人,有多少人真的將related work分析好,並選出他們心中最滿意的方法,再針對此方法做必要的修改?沒辦法,我尚來是人性本惡的觀點,容易做此聯想。至於自己,則是愈讀愈汗顏,沒想到單一領域的發展如此深廣,以前真是太小看clustering了。真的要做學術研究的話,也是可以達到很理想的境界,看到這樣的好書,讓我對學界的興趣提高了些。

只是理想抱持太高的話,永遠踏不出第一步吧。忽然對以前看過一堆給研究生建議的文章有所體會,幾乎每一篇都強調不要好高鶩遠,不然只會自挫銳氣。讓我想起和大中聊研究時,大中也提出做研究像是小步前進的觀點,勸我標準別定大苛反而失去興趣。但反向來看,有勇於挑戰的氣魄,才有機會大步邁進,試了不見得會成功,但不試是不可能成功的。

原本只是想讚賞這本書寫得太棒了,後半變得有點嘴炮。btw,有些人認為學界有許多人像是自己圈一塊地方出來自己玩自己的,我也如此認為。但是,有玩得差勁的業餘玩家,也有玩得令人讚賞的大師級玩家。能看到大師的行事風格,總是能激起一些對學界的熱情,只是維持不了多久就是了。

2007年8月18日 星期六

Bill Gross真是有趣的人

最近在看《搜尋未來》,第五章介紹Bill Gross,一位從少年時期就有經商頭腦不斷賣公司的強者。由於他有太多點子想做,不滿於專心做一件事,或著做一陣子就會嫌無趣,在賣了幾次公司後,創了Idea Lab,有點像育成中心,Bill Gross想許多點子,由此機構協助人力、空間、經費成立新公司,做個一陣子,可能又拿去賣掉。成功地開創並賣掉一個公司已很困難了,沒想到竟然有持續賣公司賺錢的人,真強!

Bill Gross賣掉的公司裡以Overture最為有名,是第一個提出點擊廣告付費模式的公司,不過後來被Google沿用後,反而被Google幹掉了,最後以十六億多美元的金額被Yahoo收購。近年來許多Blogger用的SNAP,也是Gross的作品,這個2004年秋天產生的公司,提出了新的搜尋付費模式,Gross在《搜尋未來》裡說他有信心成功。本書的原文版出版於2005/09,沒有足夠資料分析SNAP的概況,總之SNAP算現在進行式的產品,不知道後續發展如何,真有意思。

Range Search的演算法

原本找到kd-tree覺得夠威了,沒想到還有很多有趣的相關研究。像是”Data Structures for Range Searching”鞭闢入理地分析了6種方法,針對hyperrectangle range query (或稱orthogonal range search)的time complexity、建data structure的time complexity和所需的space complexity,簡潔易懂。結論是一般來說kd-tree最適用,cell(切成格狀)在特殊條件下最適用。

摘錄自1.8 Comparison of Methods:

Both the cell and k-d tree structures are appropriate in situations where the query restricts several of the attributes. If the approximate size and shape of the queries are roughly constant and known in advance, then cells defined by a fixed grid with size and shape similar to those of the expected queries is most advantageous. For queries with sizes and shapes that differ considerably from the design,

For most applications of range searching that are not characterized in the preceding paragraphs, k-d trees are likely to be the method of choice.

但這篇沒提到R-tree,也許那時R-tree還沒發明,得再評估一下R-tree的可能性。

關於演算法的早期研究就是這麼美麗、完備,但現在也沒什麼發展空間,只能拿來用就是了,cite ”Data Structures for Range Searching”的兩篇range query延伸研究分別是“On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures”和”Improving the performance of multidimensional search using fingers”,前者看來像理論分析,後者則是實作分析。

原本感到奇怪,為什麼這些研究都是用orthogonal range search,而不是圓形(球形)的range query,後來才想通,圓形的range query可以先用正方形的range query取出資料,再用圓形的條件去掉多餘的資料即可,效率分析差異不大。

2007年8月16日 星期四

半年來用Ruby的觀感

原本想把《Programming Ruby》K一K後再來寫心得,轉念想想,正因為學得不夠深,心境貼近,才能寫出未入門也感興趣的心得文;另一方面,照我在技術方面待學清單來看,不知那天才會輪到讀這本書,還是先寫心得吧。

今年寒假時,受到《Beyond Java》的鼓吹,對Ruby燃起興趣,那段期間一邊學Ruby一邊學Rails,做完一個網站,賺一筆工讀費,接著在過年回家期間花了一週啃完《Programming Ruby》Part I,之後開始漫長的實戰之旅。

寒假讀了這些書後,覺得投資Ruby前景看好,依我個人寫程式習慣,可分為三類:

  1. 處理文件雜事的小程式,一般用Perl、awk、shell script等雜項工具打發。
  2. 寫個人網頁、接case,一般用PHP打發。
  3. 寫作業、做研究用途,一般用C或Java,規模小的用C,大的用Java。

但Ruby將三個願望一次滿足!Ruby身為Perl的後續者,Perl有的能力差不多都有,只是lib比不上CPAN,不過前景看好,不用擔心這個;Rails這殺手級framework不需多介紹,用PHP寫一堆重覆零亂的程式後,我已厭倦用PHP寫網頁;至於Java,唯一的不滿是笨重,在《Beyond Java》的心得裡有些討論。

這半年來我確實全都用Ruby搞定要做的事,用Ruby寫比賽用的網頁和後端程式、用Ruby抓Web data、用Ruby實作研究用的演算法、用Ruby處理文字檔。each和map愈用愈多,去掉語意不明的for loop,改用語意明確的一行code搞定,還有配合irb這個runtime interpreter,即時測試method用法,或處理小資料,相當方便。半年前投資Ruby的決定至少幫我省下一半coding時間,當然,愉快度也提高一倍以上。唯一的不滿是Ruby沒有直接支援UTF-8,相較於Python,這是很大的弱點。

接下來要找個時段好好地讀《Programming Ruby》,學習更進階的用法,發揮Ruby更大的功效。

另外,我不覺得Python不好,之前和Scott討論後,覺得兩者大同小異,只是剛好寫慣了Ruby,暫時不會嘗試Python,個人稍微嫌Python要打的code多了一點,寫起來爽快度低了一點,不過玩Python也是遲早的事,唔...還有在淹沒在待學清單裡的Haskell。

ps

用一個語言與否,個人認為主要考量是語言的特性、既有lib的質與量,以及開發社群。以C#來說,開發社群是MicroSoft,以Perl來說,是廣大的OpenSource族群,開發社群決定語言的未來。這半年來JRuby有不少消息,透過良好的商業發展,Ruby和JVM的完美結合指日可待,JRuby的完成,等於立即幫Ruby裝上數卡車的火藥,威力倍增,Java有的lib都能被Ruby使用!所以這半年來不論從那個方面來看,我對Ruby的信心又更高了。

2007年8月8日 星期三

台北24H渡假記

最近忙著趕研究進度(還有看完《誰是接班人》第一季,大力推薦!),總覺得花個半小時寫Blog不如拿來讀些related work,結果就積了一堆文章沒寫。這篇是上週六(8/4)的事了。

原本想趁週六日衝研究進度才留在新竹的,無奈工三停電,無法取資料出來看,要趕進度也不太方便。將近中午時接到 D 的電話,說下午要不要去Mr. P家玩,還說他己和 P 講好了,可能會住 P 家,看我要不要當個驚喜,和他一起殺到他家,再大刺刺地說「哈囉,我來玩了,我今天也要住這哦!」。雖說 D 的提案聽來很有趣,但做為一個驚喜,有不少風險,所以還是先打電話給 P ,報備完再出門。

下午兩點看天色變了,就和 D 提早出門,搭客運回台北,到台北後憑著不太確定的消息搭公車前往 P 家,結果和 D 聊太專注而坐過站,幸好 E 提早發現,「只有」坐到南松山去,如果是我一人坐過站的話,大概會越過松山火車站逛逛吧,畢竟是小時候長大的地方,真令人懷念。返程加倍注意,安然抵達 P 家附近的站牌,看到 P 在站牌等我們。到 P 家後,看起來還不賴,雖然住在高樓,但沒啥高樓的感覺,在台北水泥建築裡,不管是住2F還是20F,大概看起來都是一個樣吧,只有地震時才會有不同感受。

一看到 P 的42″ 液晶電視,我馬上試著打B看看,果然感覺相當怪異,看網頁也很怪異,不過若習慣和人簡報,操作不是用鍵盤和滑鼠的話,用大螢幕上網應該不會這麼突兀。晚餐前 P 在看一些奇怪的節目,像什麼《棒棒堂男孩》,除了 P 以外,我們都無法理解這節目的笑點。晚餐在樓下解決,附近有不少吃的,而且有一家路邊攤賣素食麵和滷味,我買了炒麵和炸杏鮑菇,麵的味道還過得去,但我還是第一次吃到這麼不好吃的炸杏鮑菇。

晚餐後看 D 帶來的悶片, P 還看到睡覺,片子看不到一半大家受不了了,改看動作片,果然大螢幕就是要配爆炸飛車之類的,人多才能顯出大螢幕的好。看完電影改打Wii,一開始當然是玩Wii Sports,網球打一陣子後 D 愈打愈順,我則是一開始實力超弱,大概只有上週三lab辦Wii網球大賽時的一半實力吧,後來和 D 互有勝負,最後還是讓 D 霸台了。接著 P 讓我用Wii測體能,出來結果是43歲...,再來改玩百瓶保齡球。

大家本來就不是愛玩電動的人,玩到沒啥好玩時,就讓我圓Zelda的夢了,終於,可以玩到《Zelda:Twilight Princess》!遊戲的中文翻成曙光公主,雖然這名稱比較好聽,但從劇情來看,稱為黃昏公主可能正確一些。我憑著破破的日文勉強從頭玩到拿釣竿,由於其他人只能看著我玩,不好意思卡關太久,中途請 D 幫忙查查攻略,加快遊戲進展,增加觀眾的興趣。後來明明拿到釣竿,裝備欄上卻沒有出現,而遲遲無法進入下一步,大家都累了各自倒在床上、沙發上睡著了,我實在很不甘心,找了攻略影片,對照影片的每一步來看,發現我該做的都做了,只是影片裡真的有拿到釣竿,而我沒有,推測是Wii的bug。於是我讀別人的進度,體驗一下揮劍的樂趣後,在清晨三四點時,也倒下去睡了。

早上七點多, D 的鬧鐘響了,因為前一天他調七點要看王建民打球忘了關...,但只有吵到我和他的樣子。十點半時,我第一個醒來,接著大家跟著醒了,有人問「幾點了」,忘了是 P 還是 D 說真令人懷念,好像以前一起住學校的樣子,一個人起床後大家問著幾點了,而陸續地起床。

起床後我讀森之神殿的進度繼續打Zelda,大家在旁邊看,反正也沒啥事好做,接著看看中午新聞,和 D 重戰皮卡丘排球和小朋友下樓梯,兩者都由我大勝,用42″電視打小遊戲的感覺超怪,由於距離拉遠的關係,小遊戲的畫面感覺沒變大多少。下午大家一起回新竹啦,而 P 因為早上起床喝昨天剩下的香檳加上沒睡好,早上起來後就掛在沙發上。就這樣結束突如其來的台北24H遊。

晚上我上網看看Zelda相關消息,像是到巴哈看看中文劇情翻譯,燃起全破它的熱情,但這大概要花數十甚至上百個小時吧,記得高三時玩N64的時之笛,花了好多時間。無論如何,Zelda是必玩的好遊戲啊(和本文主旨無關的結語)!