2003
01 02 03 04 05 06 07 08 09 10 11 12
2006
01 02 03 04 05 06 07 08 09 10 11 12
2007
01 02 03 04 05 06 07 08 09 10 11 12
2008
01 02 03 04 05 06 07 08 09 10 11 12
2009
01 02 03 04 05 06 07 08 09 10 11 12
2010
01 02 03 04 05 06 07 08 09 10 11 12
2011
01 02 03 04 05 06 07 08 09 10 11 12
2017
01 02 03 04 05 06 07 08 09 10 11 12
2018
01 02 03 04 05 06 07 08 09 10 11 12
 
Jun
19
2005

一知半解、以訛傳訛

一直以來,我都認為資訊理論(Information Theory)裡面的 Shannon Entropy 是用來決定一份文件的絕對資訊量的工具。不知道從哪裡看來的,一直認為 Information Theory 就是檔案壓縮理論的全部。 上禮拜實驗室會議,我提出記憶中的一份研究,是利用壓縮軟體來做版本比較與分析,在找相關資料的過程中,我發現我把兩篇文章給混在一起了。而且我心目中的 Information Theory 就是壓縮軟體在做的事情!

直到後來老師的提醒,我才發覺,Shannon Entropy 和 Kolmogorov Complexity 是截然不同的概念。Information Theory 是類似字典的概念,他的機率是對整體出現的樣本取的。簡單的說,我們要傳輸一個訊息,這個訊息只有可能是兩個 String,是 AAAAAAAAAAAAAAAAAAAAAA 的機率是 1/2 ,是 BCFHGDOHDMZNSHJSDIWEOQLA 的機率是 1/2 ,其他都不可能,則實際我們傳輸的時候,只要傳一個 bit 就好了,0 代表 AAAAAAAAAAAAAAAAAAAAAA,1 代表 BCFHGDOHDMZNSLA。兩邊都準備一本字典,裡面寫著 0 代表什麼,1 代表什麼。

Information Theory 關心的是整體的期望值:一定要有一個樣本空間才有意義。同樣的字串在不同的空間中出現的機率不同,他們所需要的長度也不同。仔細想想,這好像很合理,原來這些年來我根本就神化了 Information Theory,逢人就說該去修修 Information Theory。 然而 Kolmogorov Complexity 就比較接近「我心目中的資訊理論應該有的樣子」了。

Kolmogorov Complexity 才是在講,一個字串所帶有的絕對資訊量是多少?用 Turing-Machine 可以把一個字串壓到多小?顯然 AAAAAAAAAAAAAAAAAAAAAA 和 BCFHGDOHDMZNSHJSDIWEOQLA 這兩者的絕對資訊量並不相等。一個很規律,一個很雜亂。規律的帶有的資訊量就少,雜亂的資訊量就多。在前面舉的例子中,他們都只有1 bit,可是若沒有字典的話,絕對不可能壓到 1 bit 那麼小。Kolmogorov 所關心的是字串本身的模式。

這個概念實在太讓我著迷了,我從以前就一直很想了解,這東西是怎麼來的?為什麼一個檔案壓縮很多次並沒有辦法讓他無止盡變小下去? 說到 Kolmogorov ,我想到我的大學同學 Lwms ,他現在延畢,在修實分析。這個領域也和 Kolmogorov 大有關係。當年修蔡聰明老師的機率論時,他就常提到 Kolmogorov 將機率論提昇到了另外一個層次,變成測度論中的一個測度。當時心中還頗為嚮往,希望高微學完以後可以把一些啥勞子 Lebesgue Integral 、測度空間等東西都繼續唸下去。可惜當初機率停修,改修系上的,而且我畢業了,現在念碩士班很忙,大概無力像 Lwms 一樣那麼幸福可以修想要修的課。

現在修 Graham、Knuth和Patashnik 的Concrete Mathematics ,都在算一些很實際、很基本的東西,summation、recurrence、series,感覺有點缺乏抽象的美。 不過老師也曾經說過,實際的東西也是很重要的,甚至比那些抽象的東西更重要。Knuth 也的確厲害,這門課也學了夠多解題技巧,值得啦。只是不知道離開了學校以後,有沒有機會再接觸抽象數學了。也許就到此為止了吧?實在有點感傷。

 

Annotations RSS

“在理論與現實中浮沈、在抽象與實際裡迷惘~”

---Anonymous. 10/20, 2005
 
 

Write Concisely