跳到主要内容

· 阅读需 8 分钟
Allen Hsieh

何謂機器學習​

對一份有特徵的資料進行判斷

舉例 人 => 身高 ,體重, 腰圍 -> 是否過重, 是否健康 過往我們依賴專家的意見，如 BMI 異常或腰圍來判斷，但這樣的判斷模式，容易受限於規模， 身高 ,體重, 腰圍, 血紅素數值, 血小板數值... 體檢列表可以列出上千上百種指數，我們也可以針對各個數值判讀，通常每個數值也會也有對應的好壞區間， 但，假設，有一種人們還不知到的特殊的連結，在身高和血紅素數值間，身高介於 150 - 155 ，血紅素數值介於 12 - 12.25 ， 有高機率患有特殊疾病， ; TODO

資料 -> 結果 = 方法​

假設有一個被設計好的判斷方法可以判別問題的結果，我們是否能夠模仿這個方法？

先決條件是：這個方法我們還未知。 如果已經知道這個方法的確切模樣，那直接套用方法就好。

大量的資料很重要，需要反覆驗證，大量練習。 想要什麼樣的結果，如果沒辦法精準定義結果，你會訓練出好像可以又好像不行的東西。

{(xn, yn)} from f -> ML -> g xn: 因 yn: 果 f: 神妙而不可知的因果關係 g: 我們對這種神妙的猜想

其中 yn 是 f 產生的。 透過 ML 找到跟 f 接近的 g。 換句話說，因果之間存在某種被規定好的關係，但這個神妙而不可知的因果關係我們沒辦法看透，所以只能透過資料和結果，自己腦補中間的關係。

可能信無限多種​

hypothesis set 找到最好的 hypothesis 我們稱之為 g

Lecture 2

Perceptron​

感知機，這個名字本身不重要，只是歷史因素遺留下來的慣用名字

g = sign(Sigma 1 ~ N(W_i X_i) - threshold) = sign(Sigma 0 ~ N(W_i X_i)) // W_0 = -threshold, X_0 = 1 = sign(W^T*X)

Lecture 10

基於二元結果的機率 - logistic regression​

想知道一個 0 ~ 1 的結果，不要二元的答案(true/false)，而是更抽象的機率(大 50% 代表更接近於 true，小於則接近 false )

執行上的困難，以及折衷作法​

實際很難拿到這種機率的真實資料(拿不到樂透號碼的開獎機率)，用 true == 1, false == 0 來當做有雜訊的答案， e.g. 如果真實機率是 0.7(70%) 那這次拿到 true 代表答案(y)為 1 但有 0.3 的雜訊，如果拿到 false 代表答案(y)為 0 但有 0.7 的雜訊

sigmoid​

用 sigmoid 函數來做分數數轉換 透過 linear regression 算出來的原始分數，帶進 sigmoid 函數轉換成 0 ~ 1 的函數

s => linear regression 算出來的原始分數 θ(s) = e^s / 1 + e^s 分母分子同乘 1/e^s = 1 / 1 + e^-s

因為 s 是 linear regression 算出來的原始分數，帶入 s = w^T x 原本 h(x) = w^T x 帶入 θ(s) h'(x) = θ(h(x)) = 1 / 1 + e^-(w^T x) 不要一堆次方符號用 exp 美化一下 = 1 / 1 + exp(-w^T x)

f(x) in logistic regression​

logistic regression 是針對結果為 true 或 false 的機率 f(x) = P(+1|X) or f(x) = P(-1|X) 可以用這個來表達 f(x) 擴展 f(x) = P(y|X), y ∈ {+1, -1}

Likelihood​

P(y|x) = P(+1|x) + P(-1|x) P(+1|x) := f(x) P(-1|x) = 1 - f(x)

注意，這裡使用的是 := (定義符號)，與等號不同的是，定義代表假設的開端， 原則上等號要具有絕對的相等意義， 但定義不同，不需要具備絕對的概念， 以這裡為例，P(+1|x) := f(x) 代表定義 +1 的機率是 f(x)， 但不代表這兩者相等，只是假定接下來的推導是以 P(+1|x) := f(x) 為前提進行下去， 反之 P(-1|x) := f(x), P(+1|x) = 1 - f(x) 也可以作為開端進行推導。

D = {(x_1, y_1),(x_2, y_2), . . . ,(x_N, y_N)} D = {(x_1, ◦),(x_2, ×), . . . ,(x_N, ×)} 這裡是在討論，當我們有真實資料 D，想向他的組成就是 x_i 對應 y_i 的資料集， 每個 y_i 不是 +1(◦) 就是(×)，可以表示成第二條式子。

probability that f generates D​

思考 D 這個資料集出現的機率，茫茫資料中出現這樣的資料組的可能性。

P(x_1)f(x_1) P(x_2)(1 − f(x_2)) ... * P(x_N)(1 − f(x_N))

參考前面的式子 f(x_i) 代表結果為 ◦， (1 − f(x_i)) 代表結果為 ×。

likelihood that h generates D​

P(x_1)h(x_1) P(x_2)(1 − h(x_2)) ... * P(x_N)(1 − h(x_N))

把 f 替換成 h，當然，h 不是 f，所以這裡想討論的是 h 有多接近 f。 所以我們會從 H (Hypothesis set) 挑一個最近像 f 的 h。 如果資料筆數夠多 (N 夠大)，h 應該會很接近 f，稱為大數似然法則。

Cross-Entropy Error​

P(x_1)f(x_1) P(x_2)(1 − f(x_2)) ... P(x_N)(1 − f(x_N)) v.s. P(x_1)h(x_1) P(x_2)(1 − h(x_2)) ... P(x_N)(1 − h(x_N))

兩者在 P(x_i) 的部分是一樣的，在後面的計算中，我們只在乎不一樣的部分 f(x_i) v.s. h(x_i)。

max of h => likelihood(logistic h) ∝ ∏(h(y_n x_n), n = 1 to N) max of w => likelihood(logistic w) ∝ ∏(θ(y_n w^T x_n), n = 1 to N) max of w ∝ ln(∏(θ(y_n w^T * x_n), n = 1 to N))

注意，這裡使用 ln 有幾個因素，

  1. 為了解決連乘(∏)，ln 可以幫助我們轉換成 sigma。
  2. 將一個函數直接套上 ln => ln(f(x)) v.s f(x) ，ln(f(x)) 的值會縮小但正相關於 f(x)，雖然函數圖形會失真，但轉換後的特性不變，這點對我們的目標沒有嚴重的影響。
  3. 整個推導最後想求的值是 min of w，ln(f(x)) 會比 f(x) 更小，就這點而言選用 ln 是有幫助的。
  4. 綜上所述，ln(f(x)) 和 f(x) 的實質意義不盡相同，但部分特性保有一制，所以選擇做出這樣的轉換。

min of w => (1/N)Σ(-ln(θ(y_n w^T x_n)), n = 1 to N)

min of w => (1/N)Σ(ln(1 + exp(y_n w^T x_n)), n = 1 to N)

· 阅读需 3 分钟
Allen Hsieh

何謂機器學習​

對一份有特徵的資料進行判斷

舉例 人 => 身高 ,體重, 腰圍 -> 是否過重, 是否健康 過往我們依賴專家的意見，如 BMI 異常或腰圍來判斷，但這樣的判斷模式，容易受限於規模， 身高 ,體重, 腰圍, 血紅素數值, 血小板數值... 體檢列表可以列出上千上百種指數，我們也可以針對各個數值判讀，通常每個數值也會也有對應的好壞區間， 但，假設，有一種人們還不知到的特殊的連結，在身高和血紅素數值間，身高介於 150 - 155 ，血紅素數值介於 12 - 12.25 ， 有高機率患有特殊疾病， ; TODO

資料 -> 結果 = 方法​

假設有一個被設計好的判斷方法可以判別問題的結果，我們是否能夠模仿這個方法？

先決條件是：這個方法我們還未知。 如果已經知道這個方法的確切模樣，那直接套用方法就好。

大量的資料很重要，需要反覆驗證，大量練習。 想要什麼樣的結果，如果沒辦法精準定義結果，你會訓練出好像可以又好像不行的東西。

{(xn, yn)} from f -> ML -> g xn: 因 yn: 果 f: 神妙而不可知的因果關係 g: 我們對這種神妙的猜想

其中 yn 是 f 產生的。 透過 ML 找到跟 f 接近的 g。 換句話說，因果之間存在某種被規定好的關係，但這個神妙而不可知的因果關係我們沒辦法看透，所以只能透過資料和結果，自己腦補中間的關係。

可能信無限多種​

hypothesis set 找到最好的 hypothesis 我們稱之為 g

Lecture 2

Perceptron​

感知機，這個名字本身不重要，只是歷史因素遺留下來的慣用名字

g = sign(Sigma 1 ~ N(W_i X_i) - threshold) = sign(Sigma 0 ~ N(W_i X_i)) // W_0 = -threshold, X_0 = 1 = sign(W^T*X)

· 阅读需 1 分钟
Allen Hsieh

Simple Kaffa

TA Coffee

ALL DAY ROASTING COMPANY

RUFOUS COFFEE

佩洛瑟

聞山咖啡

GABEE

慢動作

羊毛與花

翌日

鴉埠

達文西

James House

瑰夏

某咖啡

balance

· 阅读需 4 分钟
Allen Hsieh

10013 Super long sums​

date: 07/14​

code​

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n-- > 0) {
        int len;
        cin >> len;
        string a = "";
        string b = "";
        for (int i = 0; i < len; i += 1) {
            char tempA, tempB;
            cin >> tempA >> tempB;
            a += tempA;
            b += tempB;
        }
        int carry = 0;
        for (int i = len - 1; i >= 0; i -= 1) {
            int n1 = a[i] - '0';
            int n2 = b[i] - '0';
            int temp = n1 + n2 + carry;
            carry = temp > 9 ? 1 : 0;
            temp -= carry * 10;
            a[i] = '0' + temp;
        }
        cout << a << endl;
        if (n > 0) {
            cout << endl;
        }
    }
    return 0;
}

comment​

經典題目大數加法，利用 array 或 string 這類的序列資料結構，存每個位元的資訊，在依序對每個位元進行加法運算，得到加法結果後在分成進位位元和當前位元。

10034 Freckles​

date: 07/15​

code​

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Point
{
    int root;
    double x;
    double y;
};

struct Line
{
    int indexStart; // smallest
    int indexEnd;   // greatest
    double distance;
};

bool compareByLength(const Line &a, const Line &b)
{
    return a.distance > b.distance;
}

int main()
{
    int n;
    cin >> n;
    while (true)
    {
        int len;
        cin >> len;

        Point points[len];
        vector<Line> lines;

        for (int i = 0; i < len; i += 1)
        {
            Point point;
            cin >> point.x >> point.y;
            point.root = i;
            points[i] = point;
        }

        for (int i = 0; i < len; i += 1)
        {
            for (int j = i + 1; j < len; j += 1)
            {
                Line line;
                line.indexStart = i;
                line.indexEnd = j;
                line.distance = sqrt(pow(abs(points[i].x - points[j].x), 2) + pow(abs(points[i].y - points[j].y), 2));
                lines.push_back(line);
            }
        }

        sort(lines.begin(), lines.end(), compareByLength);

        double ans = 0;
        while (true)
        {
            Line line = lines.back();
            lines.pop_back();

            if (points[line.indexStart].root == points[line.indexEnd].root)
                continue;
            ans += line.distance;

            int root2 = points[line.indexEnd].root;
            for (int i = 0; i < len; i++)
            {
                if (points[i].root == root2)
                {
                    points[i].root = points[line.indexStart].root;
                }
            }
            bool done = true;
            for (int i = 1; i < len; i++)
            {
                if (points[0].root != points[i].root)
                {
                    done = false;
                    break;
                }
            }
            if (done)
            {
                break;
            }
        }

        cout << round(ans * 100) / 100 << endl;
        n -= 1;
        if (n == 0) {
            break;
        }
        cout << endl;
    }
    return 0;
}

comment​

Minimum spanning tree 最小生成樹​

當有 Point 和 Line 時，且每段 Line 具有 Weight(distance, cost...)，尋找將所有 Point 連接起來且 Weight 最低的路徑圖。

figure1 圖 (1) 為所有 Point 與 Line

串起所有節點是必要條件，但難點在於尋找最低 Weight 的路徑圖。

  • 不能要冗余的路徑，當有 [A - B, B - C] 時，意味著不需要 [A - C]，因爲可以用 [A - B - C] 代替。

  • 最低成本

    figure2 圖 (2) 可以連起所有 Point。

    figure3 但圖 (3) 的 Wright 比較低。

上面的程式碼是使用暴力作法完成最低成本與節點分群的功能，但最小生成樹是經典的演算法問題，可以用一些已知的最佳實踐算法來實做。

最小生成樹介紹與算法說明