Tuesday, June 27, 2017

Basic Probability Theorem

Bernoulli Distribution vs Binomial Distribution

  • Bernoulli 事件只有兩種結果,且發生某一事件機率p的分佈
  • Binomial 事件有兩種結果,且發生某一事件機率p,發生x次,在全部n次實驗中的機率分佈
    • X~BIN(10,0.6):事件在10次實驗中,成功機率0.6,X次成功的機率分佈

Geometric Distribution

  • 事件機率已知p,事件在第x次才發生事件的機率分佈:(1-p)^(x-1)*p:有點像等比級數(幾何級數)
  • 失憶性

Pascal Distribution

  • 事件機率已知p,事件在第x次才第k次發生事件的機率分佈:
    C(x-1)取(k-1)*(1-p)^(x-k)*p^k
  • X~Pascal(k,p):事件在X次的實驗中,成功的機率p,成功k次的機率分佈

    P(X<=x) = P(Y>=k)

Posson Distribution

  • 已知頻率lambda,時間T後,發生x次的機率分佈

    可由Binomial(n→無窮大)來推導

  • 題目:
    有三個門A, B, C,其中門後有一台車,小明選中門後有車,就可以把車帶回家!
    今天小明選了A門後,主持人開了B門(空的),問小明換還是不換?
    答案:
    !!!!換!!!!
    認為最直覺的想法:你最初選車的機率為1/3,車在另外兩個門後的機率為2/3,主持人選羊以後,車在最後那張門後的機率還是原來兩張門後有車的機率,2/3。

Machine Learning-3 Types of Learning

TOPIC

  • 除了是非題(二元分類),機器學習還有哪些種類。

Learning Target

  • Multi-class Classification Learning
  • Regression Learning: output as real number
  • Structure Learning: output as structure (huge classes without explicit class definition)
    (舉例像是語音辨識,語音之間就含有隱藏不明顯的關係,是一種structure)
  • ...

Learning Type

  • Supervised Learning 監督式: all y
    - 全部資料都有標記。
    eg: classification(分類), ...
  • Unsupervised Learning 非監督式: no y
    - 沒有資料有標記。
    eg: clustering(分群), density estimation, outlier detection, ...
    (目標較分散,較難衡量好壞)
  • Semi-Supervised Learning 半監督式: some y
    - 小部分資料有標記。(可以省下很多標記成本)
  • Reinforcement Learning 強化學習:
    - 透過 reward/ punishment來訓練機器: implicit y
    (learn with implicit information, 通常是一個序列/過程)

Learning Method

  • Batch Learning
    - 一組資料一次學習完 (常見作法)
    (duck feeding)
  • Online Learning
    - 一筆一筆新資料修正的學習
    (passive sequential)
    eg: email filter, reinforcement learning
  • Active Learning
    - 標記成本很高的狀況下,希望透過機器主動問問題,減少資料的需求量。
    (question asking)
    eg: "選擇性的"找出驗證老鼠癌症最好的實驗方法。

Features

  • Concrete Features
    含有人類智慧預先處理過得輸入資料,對於機器來說是較容易學習。舉例如下:
    • 錢幣分類(大小、質量)
    • 信用卡評估(客戶資訊)
  • Raw Features
    含有最原始的物理意義輸入資料,對於機器來說較難學習。
    • 所以獲取好的Concrete Feature是非常重要的議題
      • 透過深度學習
      • 透過專家設計
  • Abstract Features
    沒有物理相關意義的輸入資料,抽象的輸入對於機器來說非常難學習。舉例如下:
    • 評分預測(使用者id, 項目id, 分數)
  • 以上三種常常會一起出現舉例如下:
    • 推薦廣告系統
      • Concrete→使用者資料
      • Raw→推薦的圖像廣告
      • Abstract→使用者編號,廣告編號

REF

Types of Learning :: Learning with Different Output Space @ Machine Learning Foundations

Machine Learning-2 Learning to Answer Yes/No

Perceptrons Learning Algorithm (PLA)

  • 就是一種 linear (binary) classifiers (二分學習演算法)

How

  • IDEAS: 我們無法一開始就知道正確的hypothesis function g,於是就先找一個g0當作起點,過程不斷透過犯錯的資料來調整,直到錯誤減少到一定程度。
    (A fault confessed is half redressed - 知錯能改善莫大焉)

一定會收斂媽


  • 假設是線性可分的狀況下,確實會收斂
  • 證明:

    • 但現實問題中,即使是線性的,資料中也會有雜訊(noise)導致問題變成非線性。可用Pocket PLA來嘗試解決(把最好的留在pocket,但會比PLA慢,因為多了比較的動作)

    REF


    Dynamic Programming

    Dynamic Programming

    • DP 
    • Careful Brute Force
    • Sub-problems + memorization + Reuse + guessing
    • Must be DAG (Directed Acyclic Graph)

    Fibonacci Example

    假設想求取F(n),過程中F(n-3) 會重算兩次
    →直覺的想法就是算了第一次以後存起來,以後可以直接用,不用在往下算。
    • Recursive想法:
      • T(n) = T(n-1) + T(n-2) +T(1)
        >= 2(T(n-2))
      • Time = O(2^(n/2)) exponential time cost
    • DP想法:
      • 只需要把F(1),F(2),...,F(n)每個都呼叫一次,且每次只需要O(1) constant(把兩個子問題相加)
      • Time = O(n) linear time cost
      • Bottom-Up (實際運作時可以省下很多function call,因為沒有recursive只有loop)

    REF:






    Monday, June 26, 2017

    [C++] Passing Pareameters

    C支援Call by Value和Call by Pointer,C++多一個Call by Reference

    Call by Value

    • int main() { 
    •     int x = 5; 
    •     foo(x); 
    • }
    • void foo(int x) { 
    •     x++; 
    • }
    在"foo中的x"和"main中的x"是分開的兩個記憶體空間。

    Call by Pointer

    • int main() { 
    •     int x = 5; 
    •     foo(&x); 
    • }
    • void foo(int *x) { 
    •     (*x)++; // 指向,並加1 
    • }
    把變數的Reference傳入,foo的*x會指向這個Reference,共用同一快記憶體空間。

    Call by Reference 

    (C++新增,作用和目的雷同Call by Pointer,但在撰寫程式碼的時候方便很多,只需要在接入時多加一個&即可,特別注意int& xx; 是不行的,會出現 error: ‘xx’ declared as reference but not initialized,這個用法必定要被初始化。)
    • int main() { 
    •     int x = 5; 
    •     foo(x); // 不用加& 
    • }
    • void foo(int &x) { 
    •     x++; // 修改此x就是修改main的x 
    • }



    把變數傳入,foo的&x會指向這個變數的Reference,共用同一快記憶體空間。

    Machine Learning-1: The Learning Problem

    When can machine learn:

    • 有資料
    • 沒有明確定義的函式 (有的話就直接寫死更快不用學習了)
    • 有可能的pattern (存在潛在的規則)
    A takes D and H to get g

    Target to learn from ML:

    • target function f: 未知,理想的data→label函式
      (如果已知,就不用機器學習了)
    • hypothesis function g: 機器學習目標,"盡可能"接近f

    Terms:

    • Data Mining vs Machine Learning
      • DM: 尋找大量資料彼此之間的關係,供給人類參考依據。
      • ML: 尋找Hypothesis Function模擬預測資料和答案皆的關係。
      • 兩者其實密不可分,但傳統的DM還會研究如何有效的計算管理大量資料庫。
    • Artificial Intelligence vs Machine Learning
      • ML是實現AI的一種方式
    • Statistics vs Machine Learning
      • S是實現ML的一種方式
      • 傳統的S比較注重在數學公式的推導,但對實際計算方式探討較少。

    REF: