以複雜度理論為基礎之電腦學習理論之研究

Abstract

本計劃將探討電腦學習(Machine Learning)的理論, 特別是以複雜度(Computational Complexity)理論為基礎 之研究,我們將以Polynomial-time的觀點來探討那些 「觀念」(Concept)是可以學習的,那些觀念是不可 以學習的.除此之外,我們還將把以複雜度理論為 基礎之電腦學習理論應用在保密學上,我們的基 本想法是:保密學和電腦學習可以說是一體的兩 面,保密的主要目的是將資料編碼,以防止第三者 從經過保密的資料中得到資料的內容;也就是說, 保密的目的在防止第三者從編碼過的資料中「學 習」到真正的資料.從另一方面來看,電腦學習的目的是希望從一些相關的資料中去取得隱藏於這 些資料內的真正訊息.因此,「學習」一觀念,在保 密學中可被解釋為「破解」一保密系統;相反地, 「保密」一些資料相當於防止真正的訊息「被學 習得」.所以,如果我們能夠證明某些觀念是不可 學習的,那麼這些觀念將可被用於建構一保密系 統,而且該保密系統可「被證明」是安全的.