Where Theory Meets Practice

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

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

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

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

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

爭取

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

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

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

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

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

太過嚴肅

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

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

理論與現實

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

"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) 認為，或許聽起來很基本的「公設系統的確定性」，在現實上卻顯得天真而不切實際。他們說，或許我們是該「認真地與不確定性共處」（而橋也不必因此而崩塌）。

使用者介面與資料呈現

這一陣子，對優良的「使用者介面」(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 的「時間」特質，其實與其他維度有著本質上的不同。這就好像把時空合起來，視為四度空間一樣：看起來具有一般性，但卻因為忽略了「時間之箭」的特質，實際上最後卻反而把自己侷限住了。

或許，這也是過度執著（於抽象化），所衍生的的盲點？

再談傳教士與食人族

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

它的解答並不困難，右圖就是一種解答（在此，我用 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 來實作展示「曾感興趣的問題」，或許是恰當的呢。

歷史是什麼

前些日子看到一本小書：「歷史是什麼」（書林出版，老共學者李公明著）。

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

以下摘錄一些書中的句子（我有對部分修辭作些小更動）：

• 歷史是一則約定俗成的寓言，也是現在與過去永無止境的問答交流。「歷史」告訴人們什麼是過去，並幫助預測未來。


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


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


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


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


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

傳教士與食人族

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

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

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

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

誤打誤撞

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

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

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

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

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

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

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

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

寶刀未老？

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

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

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

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

三談 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 次」的傳說（除非我程式寫錯啦，但這也並非不可能）。那麼，這個傳言的內容，究竟是真還是假呢？

溝通是種藝術

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

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

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

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

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

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

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 這個關鍵字的呢！

回鍋第一天記事

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

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

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

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