2017年8月26日 星期六

Week6


Nearest neighbor regression

  • 資料有可能在不同區段有不同的關係存在


  • 當我們要預測一個x的value時,選擇資料中和x最接近的並將其value作為預測結果,這個方法稱為1 Nearest Neighbot (1-NN) regression


  • 如果只有一個Feature,距離很好計算,就是用兩者相減後的絕對值表示(Euclidean Distance)



  • 如果有多個Feature,那就針對各個Feature根據重要性給予權重,以下列公式計算(Scaled Euclidean Distance):



  • 用圖形化來表示1-NN (Voronoi Tessellation/Diagram) 
    • 把空間分成N個區域,每個區域裡面只有一個資料點Xi
    • 在任一區域裡面的點X最近的資料點一定是該區域的資料點
    • 對距離有不同定義,則會產生出不同結果的圖


1-NN Algorithm

  • 演算法如下,找出和所query的東西最相近的結果


  • 當資料量大而且Noise很小時預測結果會很準確


  • 在資料間隔比較大的地方會失準


  • 若Noise很大,則結果看起來像是Overfitting


k-Nearest neighbors

  • 前面提到1-NN在Noise較大時會有失準的問題,所以若能擴大計算預估值的比較資料Set比較能平衡Noise的問題。
  • k-NN Regression
    • 我們可以找出最接近的k個資料,計算其平均值來當作預測結果
  • k-NN Algorithm
    • 首先將前k個資料做距離的排序後放到一個Array
    • 從第k+1個開始到第N個資料,若比第k個資料的距離還近的話就把該資料插入到Array中
    • 最後就可以求出最接近的k個資料


  • 下圖說明使用k-NN可以減少Noise造成的影響
  • 但在左右兩邊邊界由於取的k個資料都會一樣,所以會變成相同預測值的水平直線
  • 資料量少的區域也一樣會有失準的問題



  • Discontinuities
    • 還有一個問題就是預測的結果不是連續的,當X的單位只改變1時,有可能會造成相差很多的結果。
    • 在某些應用下不能太相信此種結果,例如範例中的房價預測。

Weighted k-NN

  • 為了解決前面提到不連續的問題,我們可以把這k個結果分別取權重讓預測值更準確及smooth。


  • 要怎麼決定權重呢?
    • 距離越小者權重越高
    • 距離越大者權重越低
    • 最簡單的方式就是將權重設成
      • 1/距離

  • Kernel weights for d=1
    • 其他有一些比較複雜的設定權重方式統稱為kernel weight
    • Gaussian kernel是其中一個例子
      • 𝜆可用來設定smooth的程度
      • 它比較特別的是權重永遠不會是0
  • Kernel weights for d≥1
    • 和d=1的差別在於所帶入的距離函式

Kernel Regression

  • 不是只在NN中取權重,而是把所有的Data Point都取權重
    • 稱為Nadaraya-Watson kernel weighted average
  • 下圖是以Epanechinikov Kernel為例
    • 所選擇的Kernel會限定一個區域(圖中黃色部分),只有在這個區域內的資料才會拿來計算

  • 𝜆的選擇比Kernel的選擇還重要!
    • 𝜆代表的是所限制的區域大小(Bandwidth)
    • 𝜆太小(如圖最左)仍然會有Overfitting造成Variance增大
    • 𝜆太大(如圖最右)又過於平滑造成Bias增大
    • 𝜆的選擇也是Bias-Variance Tradeoff
  • 𝜆和k的選擇最好的方式
    • Cross Validation

Formalizing the idea of local fits

  • Global constant fit
    • 𝜆=1且所有Data Point的權重都一樣
    • 結果就會是一條水平直線
  • Locally constant fit
    • Kernel Regression屬於此種
  • Local Regression
    • 目前討論的都是locally在每個點去fit constant function
      • locally weighted averages
    • 若我們想locally在每個點去fit line/polynomial呢?
      • locally weighted linear regression
        • local linear fit
          • 減少邊界的bias但稍微增加variance
        • local quadratic fit
          • 對邊界問題無用且會增加variance
          • 減少邊界外中間區域的bias
        • 單數degree的polynomial會比偶數degree好
      • 最建議的選擇:
        • local linear regression

Discussion on k-NN and kernel regression

  • Nonparametric regression
    • Nonparametric的目標
      • 有彈性
      • 對f(x)只要做少量的假設
      • 複雜度會隨著觀測資料數量N增加而跟著增加
    • k-NN及kernel regression即為此種
    • 其他還有Splines, trees, locally weighted structured regression models…
  • Noiseless setting
    • 若資料皆沒有Noise
      • 隨著資料量越來越多
        • 1-NN Fit的MSE越來越小
      • 當資料量到無限多
        • 1-NN Fit的MSE趨近0
    • Quadratic Fit則是就算資料量到無限多,仍然不可能完全Fit函式,一定會存在Bias

  • Noisy data setting
    • 當資料量為無限多
      • k越大,NN fit的MSE越小,最後也是會趨近0

  • Large d or small N
    • NN和kernel regression在資料可以覆蓋整個space的情況下運作很好
    • 當dimension d越多,需要越多資料數N去覆蓋space
    • N = O(exp(d))才有好的performance
    • 這也是為什麼parametric model是有其用途的
  • Complexity of NN search
    • 若是採Brute force search
      • 給一個Query point xq
      • 掃過x1,x2,…, xN
      • 對1-NN來說要做O(N)次的距離計算
      • 對k-NN來說是O(Nlogk) [logk是做排序]

k-NN for classification

  • 以區分垃圾郵件為例
  • Space即為佈滿著已經分好類的email
  • Query email可藉由k-NN找出最相似的k個email
    • 看這k個email是垃圾郵件較多還是非垃圾郵件較多
    • 即可決定此郵件是哪一類










2017年8月23日 星期三

Week5

Feature selection task 


  • 若在做prediction時weight的數目超多,這樣要花大量的時間來運算
  • 若weight的數量很少(sparse),只計算weight不為0的,這樣就有比較好的efficiency
  • 另一方面來說,只加入真正跟prediction有關的feature也比較具有代表性(Interpretability)

Option 1: All subset

  • 從選擇0個Feature開始,一直到8個全選,每次都找出最小的RSS組合


  • Complexity:
    • 假設有D個Feature
    • 總共要計算的model數量為2的D+1次方 (因為包含constant)
Option2: Greedy algorithms

  • 和All subset類似,差別在於每選完一個數量的feature,選下一個數量的時候必須包含先前選的



  • Complexity
    • Steps:
      • 選0個1次
      • 選1個D次
      • 選2個D-1次
      • ...
      • 選D個1次


Regularize


  • 選擇Feature的時候使用regularization
    • 從full model開始(選擇所有feature)
    • 把某些coefficient shrink到0
    • 非0的coefficient代表所選擇的feature
  • 設定一個coefficient的threshold,小於threshold的coefficient就shrink為0



  • Lasso regression



  • Coefficient path
    • Ridge
      • 就算𝛌很大,coefficient還是很小但不會是0的值


    • Lasso
      • 可以看到𝛌還沒有到很大的數字時,就已經有好幾個coefficient被shrink為0了

Fitting the lasso regression model (for given 𝛌)


  • 由於絕對值wj無法微分,所以沒辦法算出lasso regression的closed-form solution


  • Coordinator descent



  • 對Feature做Normalize

  • Coordinate descent for unregularized regression (for normalized features)



    • Coordinator Descent演算法


  • Coordinate descent for lasso (for normalized features)

      • 演算法:



      • Threshold即為-𝛌/2到𝛌/2之間


      • 怎麼決定演算法是否收斂完成
        • 對Convex Problem來說,step會越來越小
        • 統計每次loop所有Feature的step
          • 當最大的step < 𝛆時就代表收斂完成









    2017年8月18日 星期五

    Superclasses and Subclasses


    • 假設有兩種車輛的class,有部分功能不同,但也有許多一樣的部分


    • 可以把功能相同的部分抽到Car這個Superclass,Van跟Cop是Subclass,它們去產生一個Car物件,並且在這個物件上作其他功能的新增



    • 如果是用new產生的物件呢?
    • Car是Superclass,Van是Subclass,Subclass的實作有幾點要注意
      • 使用Car.call( )將Car用到的this改綁成Van的this
      • 使用Object.create()將Van.prototype可以Delegate Car.prototype,形成Prototype Chain,如此一來Van物件才能使用Car的move method
      • 由於Van.prototype重設了,則Van.prototype.constructor會變成空的,所以也要重新將它設成Van
      • Van.prototype.grab的設定代表可以新增methods的能力



    參考資料

    https://classroom.udacity.com/courses/ud015












    Pseudoclassical Patterns


    • 若有用new來產生物件的話,JavaScript會自動加入兩行程式碼


    • 所以將重複的部分刪掉後,實際上需要留下的程式碼如下


    • 有new和之前沒有new的做法的差別在於用new的話JavaScript會多做一些效能優化

    參考資料












    Prototypal Classes


    • 下面的Code會有一個效能的問題,每產生一個Car物件,都會複製一份methods過去


    • 一個做法是使用Object.create()創造物件,就會有Prototype Chain的特性,將Car.methods帶入Object.create()中,如此一來這個Car.methods就只會有一份,所產生的每一個Car物件都會reference到同一個Car.methods


    • 有鑑於這種方式太常用,JavaScript在Object的constructor提供一個叫prototype的property,讓開發者可以將methods儲存在裡面


    • prototype這個property裡面會有constructor,指回該物件,下面的例子中Car.prototype.constructor就是指回Car
    • amy.constructor會透過Prototype Chain往上找到Car.prototype,所以也是指到Car
    • 使用instanceof operator可以看出amy是Car的instance無誤


    • 而下面的例子中,instanceof的結果會是False,這是因為fido是一個function物件,它的上一層是Object Prototype,Dog並不會在fido的Prototype Chain之中



    參考資料

    https://classroom.udacity.com/courses/ud015










    2017年8月17日 星期四

    Prototype Chain


    • 物件的複製有兩種方法
      • 建立一個空物件,將舊的物件內容一個個copy過去
      • 使用Object.create(舊物件)產生
    • 這兩者的差別在於:
      • 建立一個空物件,將舊的物件內容一個個copy過去
        • 保存的是複製當下舊物件的內容
      • 使用Object.create(舊物件)產生
        • 產生Prototype Chain若新物件沒有該資料,會到舊物件查詢
          • 如下面例子的最後一行會印出3


    • 所有物件都會有一個最上層的Prototype,稱之為Object Prototype
      • Prototype會定義一些function可以使用
    • Array則會多一層Array Prototype,這個Array Prototype的上一層也會連到Object Prototype




    參考資料

    https://classroom.udacity.com/courses/ud015










    2017年8月16日 星期三

    The Necessities of Immutable.js

    • Redux的資料都是不可修改的,一般都是用Object.asign以及Object Spread operator來達成如下:
    const state = {
      name: 'Tyler',
      age: 26,
    }
    const newState = Object.assign({}, state, {
      name: 'Mikenzi'
    })
    state.name // Tyler
    newState.name  // Mikenzi
    
    // and with Object spread
    const state = {
      name: 'Tyler',
      age: 26,
    }
    const newState = {...state, name: 'Mikenzi'}
    state.name // Tyler
    newState.name  // Mikenzi
    


    • 但是這種作法會有比較差的Performance,因為要產生一個新的Object,並且把舊的Properties複製過去
    • 改用Immutable.js可以有好很多的Performance
    • Immutable.js支援多種資料結構(List, Stack, Map, OrderedMap, Set, OrderedSet and Record)並且提供額外的API讓你可以對它作操作

    Map


    • 首先來看看Map,你可以把它視為JavaScript的一個物件,裡面放的是key-value型態的資料
    import { Map } from 'immutable'
    const me = Map({
      name: 'Tyler',
      age: 26,
      education: Map({
        elementary: 'Panorama',
        highSchool: 'Pine View',
        college: 'Brigham Young'
      })
    })
    


    • 但是它不能用.(dot)的方式來存取資料
    me.name // undefined
    me.education.highSchool // Uncaught TypeError: Cannot read property 'education' of undefined
    


    • 想要存取資料,你必須用get() method
    me.get('name') // Tyler
    me.get('age') // 26
    me.get('education').get('highSchool') // Pine View
    


    • 巢狀的資料有另一種方式存取,getIn() method
    me.getIn(['education', 'highSchool']) // Pine View
    


    • 想要修改資料的話要用set() method,它會回傳一個新的修改後的Map物件,舊的Map物件不會被修改
    // Birthday
    const newMe = me.set('age', me.get('age') + 1)
    newMe.age // 27
    me.age // 26
    


    • 想要修改巢狀資料也有setIn() method可以使用
    const newMe = me.setIn(['education', 'college'], 'N/A')
    me.education.college // Brigham Young
    newMe.education.college // N/A
    


    List

    • 你可以把List想成JavaScript的array,它提供了array常用的method如push、pop、unshift
    import { List } from 'immutable'
    const friends = List(['Jake', 'Mikenzi', 'Ean'])
    


    • 以下列出一些有用的getter methods
    friends.get(0) // Jake
    friends.get(1) // Mikenzi
    friends.first() // 'Jake'
    friends.last() // 'Ean'
    friends.includes('Ean') // true
    friends.includes('Jim') // false
    friends.reverse().first() // 'Ean'
    friends.size // 3
    


    • 以下則是修改List資料的例子
    const friends = List(['Jake', 'Mikenzi', 'Ean']);
    friends.get(0) // Jake
    const newFriends = friends.set(0, 'Jacob')
    friends.get(0) // Jake
    newFriends.get(0) // Jacob
    


    • 可以用toJS() method將Immutable轉成JS的結構
    const friends = Immutable.List(['Jake', 'Mikenzi', 'Ean']);
    const newFriends = friends.delete(0)
    friends.toJS() // ['Jake', 'Mikenzi', 'Ean']
    newFriends.toJS() // ['Mikenzi', 'Ean']
    

    const friends = Immutable.List(['Jake', 'Mikenzi', 'Ean']);
    const newFriends = friends.push('Jacob')
    friends.toJS() // ['Jake', 'Mikenzi', 'Ean']
    newFriends.toJS() // ['Mikenzi', 'Ean', 'Jacob']
    

    const friends = Immutable.List(['Jake', 'Mikenzi', 'Ean']);
    const newFriends = friends.unshift('Jacob')
    friends.toJS() // ['Jake', 'Mikenzi', 'Ean']
    newFriends.toJS() // ['Jacob', 'Jake', 'Mikenzi', 'Ean']
    


    • 相對的Immutable也有fromJS() method將JS結構轉成Immutable結構,它會遞迴地掃過每個property,若是物件就轉成Map,若是Array就轉成List
    const state = fromJS({
      name: 'Tyler',
      age: 26,
      friends: ['Jake', 'Mikenzi', 'Ean'],
      education: {
        elementary: 'Panorama',
        highSchool: 'Pine View',
        college: 'N/A'
      }
    })
    

    2017年8月13日 星期日

    Week4

    Overfitting of polynomial regression

    • 通常overfitting會伴隨著數字很大的Coefficient
    • 觀測資料的數目與overfitting的關係
      • 資料數目小(N小)
        • 當Model的複雜度增加時很快就會overfit
      • 資料數目大(N大)
        • 較不會overfit
    • Feature數目與overfitting的關係
      • 1個Feature
        • Data必須包含所有代表性的例子才能避免overfit (難!!!)
      • d個Feature
        • 需要包含更多代表性的例子才能避免overfit (超難!!!)

    Adding term to cost-of-fit to prefer small coefficients

    • 在考慮Cost的時候也把Coefficient的數字考慮進來
      • measure of fit是看Model的準確度,用RSS來表示
      • measure of magnitude of coefficients就是用來避免overfit

    • 本周會focus在以Sum of squares (L2 norm)當作coefficients的統計
    • 只看Sum的話是不準確的(如有一個正很大跟一個負很大的coefficient相加後反而很小)


    • 實際在算Cost的時候會再加入一個𝛌參數,用來平衡這兩者,又稱為Ridge Regression (或L2 Regularization)


    • Bias-Variance Tradeoff



    Fitting the ridge regression model (for given λ value)

    • 以Matrix的形式重寫Total Cost

    • 計算Gradient



    • Closed-form solution



    • Gradient Descent solution
      • 在算下一個w的時候先乘上小於1的值變小,讓Coefficient不會過度膨脹



    • 最後得到以下的演算法


    K-fold Cross Validation


    • 當資料量不夠時可採用的方式
    • 首先還是需要將Test Set需要的量切出來
    • 接著把剩餘的資料分成K份,分的時候要注意資料是否是隨機的而非有順序的


    • 分別把這K組資料作為Validation Set求出Error,並計算這些Error的平均值


    • 帶入想要測試的𝛌並找出可以讓CV最小者



    • K的大小要怎麼選擇
      • 最準確的結果是讓K=N,又稱為leave-one-out cross validation
        • 計算量太大...
      • 一般來說K=5或K=10較常見 (5-Fold CV / 10-Fold CV)

    How to handle the intercept


    • 一般來說,intercept(即w0)不會造成overfitting
    • 是否要把intercept當作其他Coefficient一樣讓它變小呢?
    • 方法1: 不要把intercept變小
      • Closed-form solution




      • Gradient Descent solution



    • 方法2: Center Data First
      • 事先將資料的中心調為0,如此一來很小的intercept也沒差了
      • Step 1:
        • 將y transform為平均0
        • 跑一般的Ridge Regression


    資料來源

    https://www.coursera.org/learn/ml-regression/home/welcome