運算學習論

運算學習論（粵拼：wan6 syun3 hok6 zaap6 leon6；英文：computational learning theory，CLT）係機械學習上嘅一套理論，重點在於用數學模型模擬認知系統－人腦或者人工智能程式－做歸納嘅過程，即係研究「認知系統普遍係點樣由手上嘅（有限）數據嗰度，學識搵出一啲描述世界點運作嘅普遍法則」呢條問題^[1]^[2]。

舉個例說明，想像一個人類，佢見過嘅天鵝冚唪唥都係白色嘅，所以佢就作出咗一個歸納性嘅推論，

由「我見過嘅天鵝都係白色嘅」（有限嘅數據），
作出「全宇宙古往今來嘅天鵝冚唪唥都係白色嘅」（普遍法則）呢個推斷；

原則上，呢個過程可以出錯－可能世界上真係有黑天鵝，而個學習者只係咁啱得咁橋從來都未見過黑天鵝。基於呢個基本諗法，運算學習論會思考「要用幾多數據做學習，先至可以令推導出正確嘅普遍法則嘅機率有返咁上下高」等嘅問題，處於認知科學、人工智能同統計學嘅交界^[3]。

運算學習論同機械學習（machine learning）息息相關：事實經已說明咗，機械學習喺實用上表現好好，但由對歸納嘅邏輯分析已知，「由手上數據推斷普遍法則」呢家嘢絕對唔係冇漏洞嘅，例如係喺製作機械學習程式嚟預測股價嘅過程當中，一般都假設咗個樣本代表到總體－「手上嘅股票嘅行為」（樣本）正確噉反映到「古往今來所有嘅股票嘅行為」（總體）；運算學習論會用到大量嘅統計學技巧，分析要點做歸納先可以令得到真相嘅機會最大化，對機械學習嘅技術發展相當有幫助^[4]^[5]。

定位

機械學習呢種技術同認知系統做嘅學習嘅過程有「由數據推導出普遍法則」呢樣共通點：假設現實世界係跟隨某啲法則（rule）運行嘅，呢啲法則係冇得直接觀察嘅，學習者只能夠嘗試由觀察到嘅數據嗰度推導出呢啲法則；想像以下嘅數據，觀察緊一個人^[1]：

晴天嗎？	佢有冇朋友喺左近？	佢出唔出街食飯？
✔	✔	✔
✘	✘	✘
✔	✔	✔
✔	✘	✘

就噉睇，呢個人嘅行為背後有最少兩條可能法則：

如果「晴天」AND「佢有朋友喺左近」，先至出街食飯；
如果「晴天」OR「佢有朋友喺左近」，先至有 60% 機會出街食飯；

... 等等。理論上，觀察者冇可能知道真正嘅法則，只能夠靠手上嘅數據推斷條法則；數據能夠話到俾觀察者知一條可能法則係真嘅機會率有幾大，例：已知手上呢啲數據，

「如果『晴天』OR『佢有朋友喺左近』，就出街食飯」

冇可能係真嘅，因為第四個個案（上表入面最落嗰個）就有「晴天但嗰個人唔出街食飯」嘅情況。最嚴格噉講，可能法則嘅數量係無限嘅，但觀察者可以靠手上數據估計最有可能係真嘅法則係邊條^[1]。

呢個過程會涉及以下嘅概念：

假說（hypothesis）喺運算學習論當中係指可能嘅法則；
一個學習過程會考慮到嘅假說嘅集就係所謂嘅假說空間（hypothesis space）；
假說空間嘅豐富度反映咗學習者嘅能耐，例如有兩個用嚟做迴歸分析（regression；一種統計分析方法，簡單講就係將兩個或者以上變數畫條線表達呢啲變數之間嘅關係）嘅機械學習演算法，A 同 B；A 淨係曉處理線性嘅迴歸模型，而 B 曉處理線性同非線性嘅關係（B 嘅假說空間比較豐富），假設第啲因素不變，B 嘅能耐高過 A ^[6]^[7]。

... 等等。

概念

學習嘅過程可以想像成概念嘅形成過程：概念係指若干個個案嘅抽象化，例如一個人腦睇咗好多件相似嘅物件，嗰柞物件件件都唔同樣，不過佢發覺嗰啲物件冚唪唥都有葉同樹幹等嘅特徵，於是佢個腦就產生咗「樹」嘅概念。

家陣想像有個集，

X\ni (x_{1},x_{2},x_{3}...x_{n})

呢個集包含咗 $n$ 件需要將佢哋分類嘅物件（例：當中有啲係樹有啲唔係），個認知系統要將呢啲物件分辨邊啲係樹邊啲唔係－output 有 1（係）同 0（唔係）兩個可能值；一個概念 $C$ 係 $X$ 嘅一個子集，分類後 $C$ 會包含所有 output 值係 1 嘅 $x_{i}$ （所有屬於樹嘅個案），而 $X$ 當中唔屬 $C$ 嘅 $x_{i}$ 嘅 output 值係 0（所有唔屬於樹嘅個案）。由對人類嘅觀察都可以得知，學習嘅過程梗會涉及大量嘅概念形成過程－一個人由細到大都會係噉學識按感知到嘅事物嘅特性嚟將事物分類，增長自己對身邊嘅世界嘅認識^[8]。

睇埋

引述

↑ ^1.0 ^1.1 ^1.2 Reaching for the gut of Machine Learning: A brief intro to CLT. Towards Data Science.
↑ Kearns, M. J., Vazirani, U. V., & Vazirani, U. (1994). An introduction to computational learning theory. MIT press.
↑ Krendzelak, M., & Jakab, F. (2016, November). Fundamental principals of Computational Learning Theory. In 2016 International Conference on Emerging eLearning Technologies and Applications (ICETA) (pp. 183-188). IEEE.
↑ Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pages 351–369.
↑ Servedio, R. A., & Valiant, L. (2001). Efficient algorithms in computational learning theory. Cambridge: Harvard University.
↑ Encyclopedia of Machine Learning, H (PDF).
↑ De Raedt, L. (1992). Interactive theory revision: An inductive logic programming approach. London: Academic Press
↑ COMPUTATIONAL LEARNING THEORY.

拎

Reaching for the gut of Machine Learning: A brief intro to CLT. Towards Data Science.
Basics of Bayesian inference.

[towardsdatascience-1] 1.0 ^1.1 ^1.2 Reaching for the gut of Machine Learning: A brief intro to CLT. Towards Data Science.

[2] Kearns, M. J., Vazirani, U. V., & Vazirani, U. (1994). An introduction to computational learning theory. MIT press.

[3] Krendzelak, M., & Jakab, F. (2016, November). Fundamental principals of Computational Learning Theory. In 2016 International Conference on Emerging eLearning Technologies and Applications (ICETA) (pp. 183-188). IEEE.

[4] Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pages 351–369.

[servediovaliant2001-5] Servedio, R. A., & Valiant, L. (2001). Efficient algorithms in computational learning theory. Cambridge: Harvard University.

[6] Encyclopedia of Machine Learning, H (PDF).

[7] De Raedt, L. (1992). Interactive theory revision: An inductive logic programming approach. London: Academic Press

[8] COMPUTATIONAL LEARNING THEORY.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]