2006年10月29日 星期日

「二十一世紀的運算」-學術研討會,A Modern Theory of Trust-but-Verify

先聲明一下,我的寫作習慣是將講者的意思經自己的思考融入後,以自己的觀點描述出來,不見得表示原講者就是這麼說。

第二位講者是姚期智院士 Andrew Chi-Chih Yao,唯一得到Turing Award的華人,相當有學者風範的人,這點在Q&A時特別感受得到,回答問題的第一件事是:”先讓我重述你的問題,確定我是否有弄懂你的意思...”,可惜姚院士是講理論,沒有相關背景很難明白,所以問的人問得莫名其妙,回答時有點雞同鴨講。

我有幸於四下時修了sctsai老師的Randomized Algorithm,加上幾前週在seminar聽到呂及人博士演講,今天姚院士的演講和呂及人博士講的課題差不多,差別在於姚院士用系統化的流程點出”Trust-but-Verify”。

40分鐘左右的演講分成四個段落,可說是今天演講裡最有系統,會讓人想看slide的演講,但是...為什麼不用中文講啊?

I. Transform of Knowledge

主旨是”讓你相信我了解這事”,比方老警探聲稱:”我閒一下就知道誰是壞人誰是好人”,但他無法系統化的證明給你看,他只能藉多次事件證明他確實有這能力(當然,姚院士不是舉這個例子)。比方有兩杖硬幣,一真一假,常人無法分辨,路人甲說他有能力判斷,但很難說明。在你知道答案的前提下,可以隨機取其中一個問路人甲,這是真的還假的,顯然路人甲只有1/2機率能猜對,連玩 N 次都被猜中的機率是 1/(2^N),比方20次全中的機率只有百萬分之一,在這樣的前提下,我們有很大的”證據”相信路人甲有能力判斷。

這有很多相關想法,像是密碼學中講的zero-knowledge proof,在不讓對方獲知任何資訊的情況下證明一件事,實例是身份辨別。或是用演化計算(Evolutionary Computation)產生判斷下棋殘局的程式,演化計算的”產物”,通常是人類無法讀懂的程式(演算法),若我們能經由實驗和機率分析得知這個程式以極低的機率(可能比隕石擊中你家還低)完全答對殘局的結果,那我們確實可以相信這個程式有能力判斷殘局,就可以在無法理解卻信任的情況下使用它

The Interactive Proof Theorem:Any game has a convincing efficient Interactive Proof.

這裡強調的Interactive Proof,是用實測證明,而不是用理論證明,對我來說是是很有新意的想法,用理論的方式證明實務的做法,和一般測試的含意不同,有興趣了解這類思維,可以看看Randomized Algorithm的書。但還是要注意測試的方式確實會影響結果,比方輸入隨機兩個數字給排序程式,測個三萬次都對也只能證明這個排序程式有正確的比大小(comparison)能力,不表示它有能力做一般排序(輸入三個數字以上)。

II. Probabilistic Checkable Proofs

問題描述:別人寫了500頁的證明,你就得讀500頁的證明才能判斷證明是否正確。希望能做到隨機讀一小段,比方某頁的4行描述,就能驗證原證明有很大的機率正確。

上次呂及人博士講這個時我做一些質疑,呂博士說實際使用沒這麼簡單,要將待驗證的證明轉為Probabilistic Checkable Proofs規定的格式,才能讓Probabilistic Checkable Proofs Verifier驗證。不管是上次還是這次,我都聽不懂。

III. Application to Software Download

given program, certificate,verifier(program, verifier) will output true or false,藉由verifier驗證program是否安全,現行的做法是用MD5演算法將program產生很小的字串,下載program後,執行MD5(program),看結果和網站上的MD5 message是否一致。不過姚院士這裡指certifiacte >> program,和現行制度大大相反,在這樣的前提下,想想是否可以不用certificate就能做到驗證,也就是verifier(program)就能做出正確判斷,這個講題和Probabilistic Checkable Proofs相關。

IV. Conclusion

Trust-but-verify,讓人”相信(trust)”的成本是遠低於”驗證(verify)”的,證明很難完成,完成後又很難驗證證明的正確性,理論研究不見得都要用寫證明(proof)的方式做驗證(verify),可以用Interactive Proof的方式使人信服(trust)而願意使用。

個人心得

姚院士的講題算是這個領域較一般性的說明,之前或多或少聽過,沒能有更多的知識增進有點可惜,但能看到學者風範的談吐,演講和回答問題的態度,讓我直接感受到言教身教,咦?我好像愈寫愈把心中姚院士的形象美化++了 XD

沒有留言:

張貼留言