機器學習的難題

除了線性代數與矩陣理論,多年以來我在交大電機系還開授一門研究所課程:智慧型資料分析 (Intelligent data analysis),此課程與機器學習 (machine learning),數據挖掘 (data mining,又譯為資料探勘) 和統計學習 (statistical learning) 多所重疊。以下是維基百科對機器學習領域的介紹[1]

機器學習是近20多年興起的一門多領域交叉學科,涉及機率論、統計學、逼近論、凸分析、演算法複雜度理論等多門學科。機器學習理論主要是設計和分析一些讓計算機可以自動「學習」的演算法。機器學習演算法是一類從數據中自動分析獲得規律,並利用規律對未知數據進行預測的演算法。因為學習演算法中涉及了大量的統計學理論,機器學習與統計推斷學聯繫尤為密切,也被稱為統計學習理論。演算法設計方面,機器學習理論關注可以實現的,行之有效的學習演算法。很多推論問題屬於無程序可循難度,所以部分的機器學習研究是開發容易處理的近似演算法。

 
為了使電腦能夠解決問題,我們需要一個演算法。如果我要解線性方程 A\mathbf{x}=\mathbf{b},高斯消去法即是一個適用的演算法。但許多現實問題常缺乏精準有效的演算法,例如,偵測垃圾郵件 (spam),也就是區分出哪些郵件是「不請自來、強行投入信箱的垃圾郵件」,這時機器學習便可派上用場。因為垃圾郵件的內容常包含成人廣告、商業網站或個人網站廣告、賺錢信息、連環信等,多數反垃圾郵件系統便根據郵件的內容來區分判別。設想我著手設計一套個人專用的反垃圾郵件系統:首先根據郵箱中垃圾郵件與正常郵件的比例,如5:4,我抽樣整理出一份「訓練資料」,假設有100封垃圾郵件和80封正常郵件。下一步是對每封訓練郵件分析並萃取特徵,計算字詞頻率是最常見的一種方法。接著我從眾多分類系統中挑選一個分類器 (譬如,分類樹),然後啟動學習程序,目的是找出真正有用的特徵並得到一組效果最佳的分類規則,可能產生的規則如下:「若『免費』的詞頻大於3%,且『輕鬆賺錢』出現至少兩次,則歸為垃圾郵件。」最後還要分析效能,針對另一份「測試資料」,計算棄真 (正常郵件被誤判為垃圾郵件) 比例有多少,取偽 (垃圾郵件被判為正常郵件) 比例又有多少。上述這套系統建構流程至今已發展出許多成功應用,如維基百科所述[1]

機器學習已經有了十分廣泛的應用,例如:數據挖掘、計算機視覺、自然語言處理、生物特徵識別、搜索引擎、醫學診斷、檢測信用卡欺詐、證券市場分析、DNA 序列測序、語音和手寫識別、戰略遊戲和機器人運用。

 
不過,我們千萬不要樂觀地認為終有一天機器學習能夠像人類一樣無所不學。美國加州大學柏克萊分校哲學系教授德雷弗斯 (Hubert L. Dreyfus) 於1972年出版《電腦仍不能做的事》(What Computers Still Can’t Do),附標題是「人工推理的批評」(A Critique of Artificial Reason),論稱人工智慧無法模仿人類高階心智功能。此書問世後立刻引起了人工智慧學界的一陣騷動,隨之受到廣泛的抨擊與撻伐。儘管如此,仍有不少人默默地研讀此書,我也是其中之一。每隔一陣子,我總會從書架上取出這本早已被世人遺忘的泛黃小書,隨意瀏覽翻閱。下面抄錄一段作者引述賽爾弗里奇 (Oliver G. Selfridge) 和奈瑟 (Ulric Neisser) 兩人於50年前發表的論文〈圖形識別機〉(Pattern Recognition by Machine,見 Computers and Thought,1963,頁250) 其中一段申論[2]

“The most important learning process of all is still untouched: No current program can generate test features of its own. The effectiveness of all of them is forever restricted by the ingenuity or arbitrariness of their programmers. We can barely guess how this restriction might be overcome. Until it is, ‘artificial intelligence’ will remain tainted with artifice.”

 
人工智慧最受批評之處在於現今程式仍然無法自行產生可供檢測的「特徵」(feature) 或「假說」(hypothesis),致使系統效用完全取決程式設計者個人的創造力。下面我舉兩個例子供讀者思考 (取自[3])。坦白講,我不認為當今有任何機器學習程式能夠透過學習過程發覺這兩筆訓練資料隱藏的規則。讀者朋友們可以將妳 (你) 們想到的答案寫在迴響欄內,並簡述分類與序列生成規則。

 
問題一:訓練資料包含數字0至14,並分為如下三類。
第一類:0, 3, 6, 8, 9
第二類:1, 4, 7, 11, 14
第三類:2, 5, 10, 12, 13
請問接下來三個數15, 16, 17應歸為何類?

 
問題二:訓練資料包含以下序列,請於?列填入適當的數字 (?共有幾個數字並未給定)。
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
? ? ? ? ? ? ? ? ? ?

 
補充一個紅利問題 (同樣取自[3])。

問題三:訓練資料包含英文字母的前13個字母,分為如下四類。
第一類:A, M
第二類:B, C, D, E, K
第三類:F, G, J, L
第四類:H, I
請問其餘13個英文字母應歸為何類?

 
參考來源:
[1] http://zh.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0
[2] Hubert, L. Dreyfus, What Computers Still Can’t Do, MIT Press, Third Printing, 1993.
[3] Erwin Brecher, Journey Through Puzzleland, Pan Books, 1994.

Advertisements
This entry was posted in 隨筆雜談 and tagged , . Bookmark the permalink.

15 則回應給 機器學習的難題

  1. ccjou 說:

    原來的問題二打印錯誤,已經訂正。注意,問題並未限制?列共有幾個數字。

    此外,我將問題一的訓練資料擴充為0至14,分成三類。

  2. Chenlogy 說:

    周老師,我發現把光碟中的WAV 檔直接Copy出來 放在電腦主機播放的效果比較好…

    優點:
    1.可以調整播放速度
    2.老師說話音量變大(感覺)
    3.可以邊看PDF檔
    4.避免掉Notebook光碟機噪音與振動問題

    • ccjou 說:

      謝謝你提供的訊息。過去在校閱時,我也是一邊播放出版社提供的毛片(wav檔),一邊參照講義本。

  3. levinc417 說:

    我沒學過機器學習,不過一個外行人的問題: 真實世界多存在隨機過程,依靠規律的機器學習是否能有效的近似?

    • ccjou 說:

      上文維基百科舉出的應用實例多可用隨機模型表述,因此屬於機器學習能夠解決的範疇。但我給的那兩個例子看似隨機其實不然,也就是說有確定性的(deterministic)分類或生成規則。

  4. Watt Lin 說:

    問題一,我還沒想到完整答案,初步推測,僅供參考。
    17大概可歸在第二類,整個看起來1, 4, 7, 11, 14, 17,個位數是 3n+1。
    15 可能屬於第三類, 5, 10, 15 五的倍數在其中,但是2, 12, 13 我不會解釋。
    16 要放在哪裡?我還沒找到規則。

    • ccjou 說:

      多數人 (當然包括我) 看到“數字”後的直覺反應是尋找一個數學分類規則,沒學過阿拉伯數字的外星人或還沒上學的小朋友則會設法尋找“各式各樣”的可能規則。

      • Watt Lin 說:

        老師是提示用「形狀」分類嗎?與數量無關?
        我尚未想到答案。

        • ccjou 說:

          這兩個問題取自一本謎題書,作者在介紹第二個問題時說道:“我從一個Mensa會員那兒聽到這個謎題,而他是多年前在荷蘭舉行的數學會議上聽說的。後來我將問題轉述給一位朋友,他未能解決,便將問題帶去他所屬的俱樂部。會員們花了幾個小時仍沒成功。最後,一位會員又將問題拿回家告訴12歲的兒子,他兒子用了5分鐘找到答案。”這兩個問題都是這種類型的問題。

  5. EMK 說:

    以下純粹個人見解:

    問題一:
    第一類:只包含曲線
    第二類:只包含直線
    第三類:包含曲線和直線

    所以,15是第三類,16是第三類,17是第二類。

    問題二:
    第一行:1
    讀出第一行:一個1,所以第二行:11
    讀出第二行:兩個1,所以第三行:21
    讀出第三行:一個2一個1,所以第四行:1211
    讀出第四行:一個1一個2兩個1,所以第五行:111221
    讀出第五行:三個1兩個2一個1,所以第六行:312211
    如此類推。

    上面最後一行:1 1 1 3 2 1 3 2 1 1
    讀出來有:三個1一個3一個2一個1一個3一個2兩個1
    即有:31131211131221

    以上純粹個人見解,請賜教。

  6. ccjou 說:

    補充一個紅利問題,歡迎讀者提供解答。

  7. EMK 說:

    猜測一:

    第一類:左右對稱
    第二類:上下對稱
    第三類:不對稱
    第四類:中心旋轉對稱

    結論:

    第一類:T, U, V, W, Y
    第二類:
    第三類:P, Q, R
    第四類:N, O, S, X, Z

    ***
    猜測二:

    第一類:左右對稱
    第二類:上下對稱
    第三類:不對稱
    第四類:左右對稱 & 上下對稱

    結論:

    第一類:T, U, V, W, Y
    第二類:
    第三類:N, P, Q, R, S, Z
    第四類:O, X

    • ccjou 說:

      感謝你的解答。我心中的答案是猜測二,還真沒想到H, I也可以按照旋轉180度對稱歸類。除了這兩種分法,不知道是否存在第三種分法?

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s