<改變世界的九大演算法> 心得

原文作者：John MacCormick
譯者：陳正芬
出版社：經濟新潮社
出版日期：2014/08/07


    這本書我借了快兩個月，有一頁沒一頁的看，然後終於被催還了。XDD

    這本算是資訊領域很好的科普書。它提到的演算法都是每天被普羅大眾所使用、解決真實世界的具體問題的偉大演算法。書裡用深入淺出的例子，說明這些演算法運作的原理。

     那它選了哪九大演算法呢？

1. Text indexing (ch2)
2. PageRank (ch3)
3. 公鑰加密 (ch4)
4. 錯誤更正碼 (ch5)
5. Pattern Recognition (ch6)
6. 資料壓縮(ch7)
7. 資料庫transaction(ch8)
8. 數位簽章(ch9)
9. 如果存在會很了不起的演算法XD

- -  -

以下為個別介紹：

1. Text indexing (ch2)
這是搜尋引擎相關的演算法。
(1) Word-location trick：存網頁中每個字的位置，就可以運用位置的鄰近與否，來判斷搜尋的相關性。
(2) 元詞技法：在標題的文字，權重提高，來判斷搜尋的相關性。

2. PageRank (ch3)
    這是也搜尋引擎相關的演算法。
    PageRank是Google引擎當初之所以能打敗其他搜尋引擎、獨領風騷的原因。它運用的是超連結技法，把一個網站的超連結視為投票，被投票越多的網站權重越高，而權重越高的網站投出去的票越有價值。整個系統可以用矩陣相乘算到一個平衡結果。
    但是整個網頁相連的結構很大，算page rank耗時很久，這時採用random walk技法可以得到近似結果。

3. 公鑰加密 (ch4)
    這是資安相關的演算法。裡面提到我們要如何透過公開的網路進行秘密通訊。主要技法是採用一個公開的公鑰，雙方各自利用公鑰將自己的訊息處理後公開，取得對方的資訊後，利用對方的資訊再處理自己的資訊。藉由不可逆的運算過程，雙方最後會得到相同的結果。
例: 公鑰basis=2,clock=11,  我:8, 對方: 9
我: (2^8) mod 11 = 3
對方: (2^9) mod 11 = 6
我公開3, 對方公開6
我: (6^8) mod 11 = 4
對方: (3^9) mod 11 = 4
兩人會得到相同的數字4
這是由於11是質數，對2^n其餘數有循環性。這就是為什麼數學上要不斷尋找更大的質數，因為質數越大，加密效果越好。

4. 錯誤更正碼 (ch5)
可靠度相關演算法。就像我們的銀行帳戶或身分證都有最後一碼檢查碼, 錯誤更正是指藉由"重複"或"冗餘"來進行錯誤檢查。其中的"漢明碼"就是一種錯誤更正碼的編碼方式。使用二維的錯誤檢查碼甚至可以直接知道錯誤碼的位置。

5. Pattern Recognition (ch6)
最經典的問題是辨識0~9的數字，可以採用如knn、decision tree等，也可以採用類神經網路。

6. 資料壓縮(ch7)
所謂的無損壓縮(lossless compression)是指找到資料的pattern、儲存pattern來取代儲存資料本身的一種資料壓縮方式。例如:AAAABBB可以存成4A3B。
有損壓縮雖然不是白吃的午餐，但是常常很划算。

7. 資料庫transaction(ch8)
ACID properties可以確保資料庫在交易時是安全的。

8. 數位簽章(ch9)
資安相關的演算法。一個軟體要經過認證, 才能確保來源是安全的。
就像我們再使用信用卡的時候, 需要透過簽名才能確保是本人。
一個契約若由某個人(或是某間公司)所認可, 它必須要能夠通過數位簽章的審核。

例:
訊息:5
假設某A選擇一數字當作鎖: 6, 選擇時鐘尺寸(質數): 11  鑰匙: 2
有一個公家銀行提供某A的時鐘尺寸和鑰匙,
5*6 mod 11 = 8, 這個8即是數位簽章
這時如果有某個人想檢驗這個8是不是某A承諾的,
它只需要將 (8*2) mod 11 = 5
若剛好等同於一開始的訊息5, 即可開鎖

9. 如果存在會很了不起的演算法 (ch10)

什麼是可計算的?
再電腦科學的領域, 這是可以被證明的問題
例如搜尋當機行為的程式不可能存在
這可以by contradiction去證明

讓我想到離散裡,
有個理髮師宣稱他將會幫「不幫自己剪頭髮的人」剪頭髮,
證明這種理髮師不存在。

《大演算》(The Master Algorithm) 心得

<大演算：機器學習的終極演算法將如何改變我們的未來，創造新紀元的文明？>

原文作者：Pedro Domingos
譯者：張正苓,胡玉城
出版社：三采
出版日期：2016/08/05


    這本書非常新，是今年夏天才出版的，用簡單扼要卻又引人入勝的方式介紹了機器學習的歷史發展、五大主要流派各自的觀點和限制，並且提出一個「大演算」(The Master Algorithm)的概念，期許且預言，各理論流派將會進行整合，形成一個The Master Algorithm，並且對我們的未來產生廣泛而深遠的影響。

    本書內容淺顯易讀，對於稍有資訊背景的人來說並不會很難懂，能稍有統計或類神經網路的知識又更好一些。

    本書提到的五大流派，是指：

1. 符號理論：

    數學上，我們習慣將現實的問題轉化成符號，用符號進行邏輯推演，再將推演的結果拿到現實中去驗證。決策樹(decision tree)就是一種將事實化成邏輯符號的例子。

2. 類神經網路：

    顧名思義是模擬人腦神經元運作模式的一種技術。將每一神經元化為一個節點，節點之間層層相連(數學上來說是以權重做線性加成，再以一個激活函數對輸出結果做調整)的一種學習器。

    此領域在1960年代曾將風光一時，研究者一開始認為可以用它來解決所有複雜問題，最後卻發現它甚至無法解決像是XOR這種簡單、但線性不可分離(Non-linear separable)的問題。

    現今隨著deep learning技術發展起來，類神經網路理論亦死灰復燃。這個流派最大的缺點就是無法對它所學習到的東西(也就是各層的weight)進行物理上的解釋，而僅僅是一堆數字，同時也很容易overfitting，但他們在實務上可以取得良好的正確率。

3. 演化論：

    遺傳演算法模擬生物學上染色體交配、突變、適者生存的法則，利用電腦母程式產生大量子程式，對不適者加以淘汰，以留下最好的學習法則。

4. 貝氏定理：

    簡單貝氏定理(Naïve Bayes)非常基礎卻非常實用，適用性非常廣。一言以蔽之，它試圖用過去的經驗(prior)和目前的事實來預測未來發生的機率(postier)。諷刺的是，它雖然簡單，卻常常比一些複雜的學習法得到更好的成效。這是機率統計的威力所在。

5. 類比推理：

    這個流派應用的例子如knn演算法、SVM(支持向量機)，藉由數據資料彼此之間的相似性(similarity)作為分類的判斷依據。


    最後它提到機器學習的未來展望。作者認為，機器學習雖會偷走人類的工作，但同時也為人類創造更多的工作。人類可以利用機器學習對現實需求便宜行事，而花費更多心力在以人為本的問題上。