星期一, 10月 31, 2005

Where Theory Meets Practice

當「理論」碰上「實際」,場景會是如何呢?

有人說,實際是理論的延伸;也有人認為,理論是實際的抽象表達。那些聰明又有名氣的思想家,不管是支持哪一種論點,都能產生許多「有用」或「影響深遠」的思想或學說。

而自己工作了這些年,卻只有一些不成熟的經驗:理論與實際雖然在許多「概念層次」的地方很相似,但是在許多「現實層次」上的建議卻常有衝突。

這完全是現實社會的成本考量嗎?似乎也不是如此。有時,對於實際很重要的許多性質(例如「軟體品質」、或者資訊檢索中的「相關概念」),似乎連理論都難以界定清楚。

在一本關於 "Distributed Systems" 的書上看到右上方的這張圖。很喜歡它對「當理論遇上實際」的描繪。藝術作品就是這樣,對現實常有詼諧幽默的表達,富有詩意,又餘味盎然。

星期五, 10月 28, 2005

爭取

昨天終於催收到應得的資遣費,很是開心。

本是應得的東西,為什麼會覺得開心呢?因為,如果沒有如此主動、積極地爭取這些該得到的權益,我很可能會在一次又一次的延後中,逐漸麻痺自己,終至最後不了了之。(以個性、或者個人習性來說,我通常會先試圖爭取;倘若不成功,則最後很可能會自行吸收損失。)

然而,現今的社會,似乎偏好懂得爭取權益的人。「好人」不見得會得到獎賞,但「臉皮厚些、懂得爭取」的人卻經常能夠獲得實質的報酬。說得刺耳些,如果懂得爭取(或者像是「被掛掉的阿尼」所說,會吵會抗議),好像常常可以拿到「不是那麼應得」的好處。

「自行吸收損失」還有一個壞處:吃了幾次虧後,如果內心沒有好的化解方式,就容易感到不平、憤怒、或者憂鬱。這些情緒累積久了,是會得到內傷的。

很高興自己終於用行動來獲取應得的權益;也很高興自己在這些現實處理面上終於「有所長進」。

星期四, 10月 27, 2005

太過嚴肅

最近寫的 Posts 沒有得到什麼回應,有些傷心 :(

我想,就如同 Sophia 所說,寫得太嚴肅啦。不過,要怎樣才能寫出詼諧、幽默、有趣的小品文、或者生活記事呢?這可真是個大難題啊。

星期三, 10月 26, 2005

理論與現實

很久以前曾匆匆看過,但現在重新回味,又別有一番風味。

"Suppose a contradiction were to be found in the axioms of set theory. Do you seriously believe that that bridge would fall down?" (假設我們發現集合論的公設有矛盾。你真的會相信,那座橋會因此而掉下來?)

集合論是形式化 (formal) 數學理論的根基。沒有集合作為基礎,就發展不出關係 (relation)、函數 (function) 等進階的定義;而從邏輯上來說,也就推導不出各式各樣的定理。但是,「萬一」集合論真的有問題,物理世界「真的」就會因此而產生巨大的變化嗎?

據說,鼎鼎大名的 Turing 是相信:橋會因此而崩解;但同樣受人推崇的維根斯坦 (Wittgenstein) 則不同意。兩位大師級的人物,對理論與現實,竟然有如此不同的看法!(可參考這網頁。它的一些註解也很有趣:誰『贏』了?看起來 Turing 是有些太過天真,但他留給我們電腦這東西。至於維根斯坦留給我們什麼?呃...就是維根斯坦。)

也有人試圖在這兩個極端間取得緩頰。"Discrete Thoughts" 的作者 (Mark Kac, Gian-Carlo Rota, Jacob T. Schwartz) 認為,或許聽起來很基本的「公設系統的確定性」,在現實上卻顯得天真而不切實際。他們說,或許我們是該「認真地與不確定性共處」(而橋也不必因此而崩塌)。

星期一, 10月 24, 2005

使用者介面與資料呈現

這一陣子,對優良的「使用者介面」(User Interface, UI) 設計,都隱隱懷有一份欣賞與讚嘆。

為什麼會這樣呢?我猜想,是因為自己這些年來,漸漸感受到 UI 的重要性。此外,自己也曾花過一些心力去思考,卻苦於找不到「漂亮的抽象模型」來說明:怎樣的 UI 設計才算是好的設計、惱於「主觀的使用者意識與客觀的資料」之間複雜難解的互動。

之前在 Maryland 求學,就曾聽說過 Shneiderman 在 UI 設計上的大名。然而,那時的我只顧著尋找計算機科學的深層內容(或許也可說是「抽象美」),對於「使用者介面」則視為是二流的學問,因此錯過了去上課求知的機會(不過,那個時候就算是修了課,因為缺少了一份「強烈的動機與感動」,應該也只能膚淺地記得課堂上的知識內容,而學不到課程的精髓罷)。

這幾天,強烈感受到需要拓寬一下自己(與實驗室成員)對資料呈現(Data Visualization,它構成一部份 UI 設計的主題)方面的知識。於是,我從書堆裡,將 Shneiderman 的一本舊書又翻找了出來。

覺得書中的一份資料應該頗有啟發性。它列出資料呈現的分類方式(Data Types)、與一些相關的工作(Tasks;從使用者角度,或可說是「使用者可執行的動作」):

Data Types
  • 1-D Linear
  • 2-D Map
  • 3-D World
  • Temporal
  • Multi-Dimensional
  • Tree
  • Network
Tasks
  • Overview:
    - Gain an overview of the entire collection.
  • Zoom:
    - Zoom in on items of interest.
  • Filter:
    - Filter out uninteresting items.
  • Details-on-demand:
    - Select an item or group and get details when needed
  • Relate:
    - View relationships among items
  • History:
    - Keep a history of actions to support undo, replay, and progressive refinement.
  • Extract:
    - Allow extraction of subcollections and of the query parameters.
看到這樣的整理歸類,至少讓我從新思考 Temporal 與 Multi-Dimensional 之間的差異。我從前一直將 Temporal 視為 Multi-Dimensional 中的一種特例(多維度中的一個維度),卻沒有關注到:Temporal 的「時間」特質,其實與其他維度有著本質上的不同。這就好像把時空合起來,視為四度空間一樣:看起來具有一般性,但卻因為忽略了「時間之箭」的特質,實際上最後卻反而把自己侷限住了。

或許,這也是過度執著(於抽象化),所衍生的的盲點?

星期四, 10月 20, 2005

再談傳教士與食人族

幾天前,曾提到「傳教士與食人族」的問題。

它的解答並不困難,右圖就是一種解答(在此,我用 B 代表「黑人」或食人族、用 W 代表「白人」或傳教士)。一開始,左岸有三個黑人、三個白人、與一艘船(用黑色的方格代表);第一步,一黑一白將船開到對岸;第二步,一個白人將船開回左岸;接下來,兩位黑人將船開到右岸,然後一個黑人把船開回來... 如此一共進行 11 步,就可以將所有人都渡到右岸。

據說,一般解不出來的人,大多是在第五步後,沒有注意到第六步 -- 這一步將辛辛苦苦度到對岸的一個黑人與一個白人度回左岸。

傳統的人工智能 (Artificial Intelligence) 相當強調問題解決 (Problem Solving),因此也經常用「簡單且經典」的益智問題當作教材,告訴學生何謂搜尋空間、以及如何有效搜尋。

從概念上來看,如何「解傳教士與食人族問題」其實相當直觀:我們只要把問題的「狀態空間」 (state space) 產生出來(作為程式的搜尋空間),然後找到一條路徑,從問題起始的狀態,通到目的狀態即可。

例如,在這個問題裡,一個狀態就是像 (1B1W, R, 2B2W) 這樣的一個 tuple(有序元,或者說是向量),它表示「有 1B1W 在左岸,2B2W 在右岸,而船停在右岸」(右上解答圖在第五步後,就是停留在此狀態)。而「傳教士與食人族」的問題,也就轉化為:尋找一條路徑,由 (3B3W, L, 0B0W) 狀態,通往 (0B0W, R, 3B3W)

至於如何實作,講穿了後其實也頗容易(這點可以日後再找機會討論)。值得一提的是,今天在 CNET 上看到一篇報導(它提到:在全球資訊網上,或許 PHP 比 Java 更有可為。但我在意的,是「簡單相當重要」這種觀念與原則)。這也讓我覺得,自己選擇用 PHP 而非 Java 來實作展示「曾感興趣的問題」,或許是恰當的呢。

星期二, 10月 18, 2005

歷史是什麼

前些日子看到一本小書:「歷史是什麼」(書林出版,老共學者李公明著)。

由於目前實驗室做的研究,有相當大的部分是在於「用電腦與數位化內容,來幫助學者研究台灣的歷史」,因此稍微了解歷史學家(可類比於資訊界常聽到的「領域專家」:domain experts)怎麼看待事情,應該會對研究的結果有些幫助。

以下摘錄一些書中的句子(我有對部分修辭作些小更動):
  • 歷史是一則約定俗成的寓言,也是現在與過去永無止境的問答交流。「歷史」告訴人們什麼是過去,並幫助預測未來。

  • 只有那些被歷史學家賦予了意義、並進入人類記憶之中的事情,才成為真正有價值的「歷史」。(衍生的問題是:歷史學家根據什麼來判斷哪些已發生的事情是有意義的呢?)

  • 與一般人相較,歷史學家是一群對歷史意識更有自覺、更主動研究過去的人;他們感到有責任把自己所了解到的過往事情,講述給更多的人。

  • 歷史學研究的對象,與自然科學所研究的對象,有著根本上的差異。歷史學家無法超越時空限制而面對過去;他們只能面對一些歷史的遺物,而這些遺物本身無所謂證明什麼,要依賴歷史學家決定用它們來說明什麼。

  • 史實並不是歷史學家研究的出發點,也不是經過挑選、並賦予意義之後就可以密封保存的。(因為現在和以後可能發生的事情,都有機會改變我們對某一史實的看法。)

  • 歷史學家的主要工作過程:收集史料、提出問題、作出解釋並予以證實。

星期一, 10月 17, 2005

傳教士與食人族

它是個不困難、但也算經典(經常被書本提起、參考)的益智問題。

這個問題的正式名稱,應該是叫做:Missionary and Cannibal(傳教士與食人族)。但小時候那裡知道什麼「傳教士」,聽到的是「通俗版語言」的「黑人與白人過河」問題。

通俗版的描述是這樣的:有三個白人與三個黑人要過河。但河邊只有一艘船,且船上最多只能容納兩個人(當然,至少需要有一個人在船上,才能將船駛到河的彼岸)。此外,還有一個條件:不管是在河的哪一邊(或是在船上),當黑人的人數超過白人時,黑人就會把白人吃掉。問題:要如何安排渡河的順序,才能夠讓此三個白人與三個黑人順利渡河?

不記得是國小、還是國中時,第一次聽到這個問題了。說也奇怪,似乎也只有在那個懵懵懂懂的年代,才會對任何需要動點腦筋的益智問題,都感到有股熱忱與衝動。不知道是不是因為年紀漸增,變得現實老成;現在對許多事情都顯得力不從心、甚至提不起勁。當然,我對許多曾感興趣的益智問題,也就失去年少時的興致,而只剩下淡淡的回味了。

星期五, 10月 14, 2005

誤打誤撞

這幾天試圖整理迷宮的 PHP 程式,讓它看起來清爽漂亮些。

「整理」的工作,大致上就是清除一些非必要(或為了除錯而加上去)的函式,在一些地方加上註解,並重寫部分的程式碼。

奇怪的是,我發現一個「違反直觀」的現象:調整「讓迷宮多轉些彎」的參數後,若「多轉彎」的機率大於「走直線」的機率,迷宮怎麼反而看起來更少曲折?(例如,右邊的兩張迷宮圖,路徑都頗「迂迴」,但下方的迷宮就比上方的迷宮有較多的轉彎。)

咦,那我之前怎麼沒有發現?當初不就是因為覺得迷宮不夠蜿蜒,才加入「轉彎」的考量啊;而且,加入轉彎的參數後,迷宮不是也「真的」更蜿蜒曲折了嗎?(參考一個月前的 posts:稍微有些曲折的迷宮更為曲折的迷宮。)

這下可有趣了。根據經驗,這要嘛是自己在實作時,把參數的意義弄反了;否則就是程式不知道哪兒寫錯了,誤打誤撞後,讓加入多轉彎參數的結果,比沒有加入參數的輸出要來得曲折。

花了許多時間追蹤,才發現真的有另一個地方出了些差錯;而「負負得正」,兩個錯誤合起來,就產生出「看似正確」的結果。

如果沒有這番整理,雖然程式仍然可以產生曲折的迷宮;但不管怎麼說,這程式其實都是實作錯誤的。有趣的是,對於「產生曲折迷宮」的目的而言,這個錯誤的程式,或許還是「無傷大雅」、甚至「合於規格」的:我們只要把參數往相反的方向調整就好了(例如,希望得到「多轉彎」的效果,本來應該把「多轉彎」的參數調高,但現在只要反向調低即可)!

程式改好後,我突然有種感覺:「誤打誤撞」似乎也是「實驗」的一種有趣特性呢。

星期三, 10月 12, 2005

寶刀未老?

今天與學弟妹討論檢索與分類後,突然有「喔,我竟然懂得還不少」的感覺。

或許是因為自己當初(做博士研究)的確曾對資訊檢索與分類深思過、或許是因為「資訊檢索」在這幾年來也進展緩慢、又或許只是因為大家並不善於表達內心深邃過人的創意;我對學弟妹們做的許多「古契書檢索」研究,在概念與系統整合上,總覺得有些「似曾相似」的味道。

而這兩個星期與學弟妹個別討論時,我竟然也幾乎都能夠在不算長(30 ~ 60 分鐘)的時間內,大致上抓到每個人研究的重點,甚至還能提供一些參考或建議。

這是否是只是種幻覺?或許,是自己一廂情願、自欺欺人地認為自己「寶刀未老」哩。

星期二, 10月 11, 2005

三談 AB-game

網路檢索到 Mastermind 相關的文章後,發現 Knuth 的方法確實可以減少猜測的次數。

我們或可將它視為一種「如何縮小可能性空間之優化處理」的方法。在先前「再談 AB-game」這篇 post 裡,提到甲每猜測一次,就可以藉由乙的回答,從「可能性空間」裡,刪除一些「不可能是答案」的數字。問題是,該猜測那個數字,才能夠排除最多不可能的答案呢?

Knuth 建議,選一個數字,讓「剩下的狀況裡,有最多可能性」的值是最小的 (choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities)。

令人困擾的是,雖然 min(max(...)) 這樣的抽象式子簡潔漂亮,但是對於我這樣非數學系背景的人,通常並無法從這樣的式子中、看出它的直觀意義。因此,對這個式子多加些解釋,應該是有助於理解的。

對於目前的「可能性空間」(也就是「不會與乙對甲先前的猜測所給的回答」衝突的所有可能答案)而言,任何甲的新猜測都可能有 14 種回答(4A0B、2A2B、1A3B、0A4B、3A0B、2A1B、1A2B、0A3B、2A0B、1A1B、0A2B、1A0B、0A1B、0A0B -- 不可能有 3A1B 的情況發生)。這 14 種回答,可以將「目前的可能性空間」切割 (partition) 成 14 個集合。

例如,假設目前的可能性空間為 S = {3749, 4379, 8095, 8590}(參考右圖),若下一步甲猜 3749,則乙只可能有三種回答:4A0B(若乙的謎底也是 3749)、1A3B(若謎底為 4379)、或者 0A1B(謎底為 8095 或 8590);其他像是 1A3B、0A4B 等等回答,都是不可能的。因此,3749 這個猜測,可以將 S 分割為 {3749}、{4379}、{8095, 8590}。

換個角度看,這樣的切割表示,經過甲的 3749 猜測後,可能性空間只能是 {3749}、{4379}、{8095, 8590} 這幾個分割中的一個。於是,我們知道:經過猜測 3749 這個數字後,「最大的可能性空間」是 {8095, 8590},而其集合的個數 (cardinality) 則為 2。

值得提醒的是,我們不見得一定要猜測可能性空間裡的數字。例如,我們可以猜 8793,它可以將 S 切分為四個 cardinality 為 1 的 partitions:回答 1A1B 的 partition 為 {8095}、回答 2A0B 的 partition 為 {8590}、0A3B 的 {4379}、以及 1A2B 的 {3749}。

Kunth 的方法,就是從所有可能的新猜測裡,選擇會讓「最大可能性空間」個數 (cardinality) 為最小的那個數字。在上面的例子中,猜測 8793 會比猜測 3749 來得好;因為前者切分出的 partitions 中,最大的 cardinality 為 1;而後者切分後,最大的 cardinality 為 2。

我也依照這個演算法實作了程式。實際跑過後,它驗證了這個演算法,對於 Mastermind 的確可以在五步內猜得答案。然而,對於 AB-game,這個演算法卻仍然可能需要猜測七次。

所以,Knuth 的演算法,並不能證明「AB-game 在最壞的狀況下,也僅需要猜 6 次」的傳說(除非我程式寫錯啦,但這也並非不可能)。那麼,這個傳言的內容,究竟是真還是假呢?

星期五, 10月 07, 2005

溝通是種藝術

好的溝通很困難。奇妙的是,當事人經常不覺得溝通是件不容易的事。

回鍋作 post doctor 的「工作」,實際上卻沒有特別想做的研究。雖然對於資訊檢索、甚至是 THDL (Taiwan History Digital Library),我仍然有著頗為濃厚的興致,但我還是想「在這一年內盡量整理從前感興趣的主題、並寫出些東西」。

就先扮演項老師與實驗室學弟妹間的橋樑吧。這個星期的主要工作,就是與實驗室的幾位學弟妹,討論他們目前的研究狀況,並適時提供一些適當的建議。

令自己覺得有些高興的是,對於溝通討論,我終於有了一些說來頗微不足道的自覺(這應該也是今年前半年在公司進行「產品改良專案」所學到的吧)。

自覺到什麼呢?雖然我在討論、詢問學弟妹們的工作內容時,仍然時常尖銳地 (sharply) 試圖從概念與模型來明確定義使用的詞彙(我多少覺得,明確的詞彙非常重要;而大家通常都在「模糊的描述中,討論模糊的未來方向」);但我有時會突然驚覺,過度尖銳的對話,對於溝通是沒有太大幫助的。

因此,溝通的技巧非常重要。我甚至覺得,溝通就像是藝術呢。如果能夠懂得欣賞溝通(就像是懂得欣賞藝術般),就應該更能欣賞對方的長處與成果、更能了解其他人的想法吧。

星期四, 10月 06, 2005

Mastermind

Mastermind 是一種很像 AB-game 的兩人遊戲。

事實上,我接觸到 Mastermind 這遊戲的時間,比 AB-game 還要早。印象中,大約在二十年前,大姊就曾買過這個益智遊戲來給家人玩了。

Mastermind 的棋盤如右圖所示。玩法是這樣的:甲先由六種非黑白顏色的釘子中,選四個排在盤面上作為謎底,然後讓乙來猜。對於每一次乙的回答,甲作如下的提示:若乙猜的顏色與位置都相同,則放上一個黑色的釘子;若乙猜的顏色對,但位置不同,則放上一個白色的釘子。與 AB-game 不同的是,Mastermind 允許出謎著選相同的顏色。因此,甲可以有 6 x 6 x 6 x 6 = 1296 種不同的謎底選擇。

例如,若甲的謎底是 BBRY(藍色、藍色、紅色、黃色),而乙的猜測是 RBGB(紅色、藍色、綠色、藍色),則甲所回應的提示就是:1B2W(一黑:第二個位置顏色相同;二白:一個藍色的位置不同、一個紅色的位置不同)。

Web 上有許多網站討論 Mastermind。例如,Invitation to Mastermind (參考 Ankh 在「再談 AB-game」的 comments),就有提到,Knuth 在 1976-77 年間,即已提出一個 algorithm,它能夠在五次猜測內取得答案。

有趣的是,雖然從一開始,我就很想檢索「跟這個遊戲相關」的文件,但由於當時並不知道 Mastermind 這個名稱,因此根本就不知道如何下合適的 query keywords。換句話說,雖然我有 user needs,也有威力強大的 Google 搜尋引擎,但是我卻仍然無法用「描述這個遊戲」的方式,來取得檢索結果。

那我是怎樣得知 Mastermind 這個關鍵字的呢?說來也奇妙,我其實是用「不知道是否為正式名稱」的 "AB-game" 去檢索,然後在檢索到的文件中,發現 Mastermind 這個關鍵字的呢!

星期一, 10月 03, 2005

回鍋第一天記事

今天是「回鍋」作 post-doctor 的第一天。

大致上來說,「工作」得還算充實;但因今天沒有睡午覺,身體有些疲累。

做了些什麼呢?與四位碩二的學弟談了談,了解他們目前在做的研究、已做出什麼成果;可能的話,也順便問問他們「接下來是否還想做些什麼」。

老師還說,電機的博理館有 FORTE (Formal Techniques for Networked and Distributed Systems) 與 ATVA(不知是什麼縮寫)的 conference,應該頗值得去聽聽看。於是,我下午也去聽了 Protocol Verification 的 session,感覺還算不錯。