Week3

• 現實中Prediction不可能完全準確，這中間一定會有一些損失產生，可以用Loss Function來計算

Training error

• RMSE (Root Mean Square Error)

• 由於Model複雜度越高越能fit training data，所以training error會越低

• 但Training error是用來評估預測的效能的好工具嗎???
• 由於Training error代表的是對training data的fit程度，除非training data具代表性可以包含所有一切的可能，否則好的training error未必代表預測是準確的

Generalization (True) Error

Test error

• 從Training set裡面取一些出來當作Test set

• Test error是把從training data上得到的Model拿來對Test data做預測，以求出Loss作為Test error

• Test error接近Generalization error只是會上下震盪
• Overfit
• 當Model複雜度已經過高導致Generalization error開始增加的情況

Training / Test split

• Training set切得太少
• 預估的Model不準確
• Test set切得太少
• Test error無法逼近Generalization error

Sources of error

• Error的來源有三種
• Noise
• Bias
• Variance
• Noise
• 資料本身就會有一些不準確的Noise產生

• Bias
• 假設我們把Model複雜度設為1，把所有可能大小的training set都拿出來算Model，並求出平均值fw bar

• Bias代表的是和實際結果的偏差程度，Model複雜度越低，和實際結果偏差會越大，也就是Bias越大

• Variance
• 把所有可能大小的training set都拿出來算Model，這些Model的變化程度代表Variance
• Model複雜度越低，變動也較小，所以Variance越低

Bias-Variance Tradeoff

Error vs. amount of data

完成Regression/ML的工作流程

• 將資料分成training data跟test data會以下列方式做Regression

• 但這樣的作法是有問題的
• Test error是根據test data求得，若test data不具代表性則可能實際上的performance是更差的
• 解決方法
• 使用兩組Test set

• 一般在切資料時會以下面的比例去切

參考資料

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

Week2

Polynomial regression

• Regression有可能不是一條直線

• 或是要考慮多個Feature

• RSS的公式如下，h(xi)代表的是第i個Data的Feature Vector，H是所有Data的Feature Matrix，w是Coefficients Vector

• RSS取Gradient的算法如下

• 接著來算最佳解，方法1是Closed-form solution，也就是把∇RSS設成0

• 方法2是Gradient Descent，首先算出對於wj做偏微分的結果

• 所以可以得出要更新第j個Feature時的式子

• 最後得到的演算法如下

參考資料

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

Week1

什麼是Regression?

• 用來從Features產生Predictions

• 可以用來預測股市、房價、或是醫學上根據腦部掃描可以用來判讀你的情緒

Simple Linear Regression Model

• f(x)為x和y之間所期望的關係，yi是實際的資料值，可以用f(x)加上ℇi的偏差來表示
• w0跟w1代表regression的coefficients

• 要怎麼評估f(x)線段多麼fit資料呢?
• 用RSS (Residual Sum of Squares)表示這條線段的Cost，它統計各資料點和線段的差異，RSS越小的線段表示預測的越準確

An aside on optimization

• 在尋求怎麼求出RSS最小的線段前，先要了解一些事情
• Concave線段指的是在上面選兩點g(a), g(b)連成一條直線，則此直線都位在g(w)之下
• Convex線段則相反，直線都位在g(w)之上
• Neither則是不屬於Concave也不屬於Convex

• 針對Concave線段，我們可以找到它的最大值，會位於對g(w)微分為0的點
• 針對Convex線段，我們可以找到它的最小值，會位於g(w)微分為0的點
• Neither類型則可能找到好幾個微分為0的點，也可能一個微分為0的點也找不到

• 在Convex線段尋找最小值可以用下列的演算法一步步求得，η代表step size

• Step size可以是固定的，但設的太大的話可能要話很多時間才能收斂完。
• 所以Step size也可以是逐漸減小的，前面用較大的Step size快速收斂，後面需要精準一點的調整所以用較小的Step size

• 而這個演算法什麼時候收斂完成呢？最好的情況是當dg/dw微分為0時代表已經找到最小值，但一般在實作時會設定一個dg/dw微分值的絕對值的Threshold，當它小於Threshold時就代表收斂完成了。

Gradient Descent

• 上面提到的是一維只考慮一個w的情況，那如果是多維的情況呢？下面是w0, w1與RSS之間的關係圖，從2D變成3D了

• 多維的情況要怎麼求最小值呢？在這邊引入Gradient的概念，若g(w)的w有p+1維，則g(w)取Gradient(以▽g(w)表示)會等於一個p+1維的vector，每個Item是g對各個w項目的偏微分，例如當對w0作偏微分時，就把w1...wp當成常數。當對w1作偏微分時，就把w0,w2...wp當成常數。

• 我們可以把前面3D的圖轉換成2D的Contour Plot

• 如果要求最小值的話，可用Gradient Descent，把前面一維例子的dg/dw換成▽g(w)，一樣是當Gradient小於Threshold時代表收斂完成

找出最好的線段

• 前面講過RSS的公式，則對其求Gradient的結果會如下(就是分別對w0,w1做偏微分)

• 找出最佳解有兩個方法，第一種就是把Gradient當作0，求出w0跟w1
• 第二種是Gradient Descent，改寫一下上面的式子，由於w0+w1xi等同於預測的值，所以Gradient可以改寫成右邊的樣式

• 最後Gradient Descent的演算法會如下

Asymmetric errors

• Symmetric Cost Functions
• 預測的結果整體比實際高或低的影響是一樣的
• Asymmetric Cost Functions
• 預測的結果整體比實際高或低的影響是不同的
• 以賣房的房價來說，預測的太高可能就沒人要買，預測的太低則會少賺

資料來源

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

Chapter 15: 泛型(Generic)

簡單的泛型

• 有些情況你會希望Container可持有多種物件型別，但實際使用上你一次只會放一種型別到此容器。
• 可以將型別參數(T)放進class名稱後的角括弧中，在實際使用此class時將T取代為真正的型別資訊。

  public class Holder3<T> {      private T a;      public Holder3(T a) { this.a = a; }      public void set(T a) { this.a = a; }      public T get() { return a; }      public static void main(String[] args) {          Holder3<Automobile> h3 =              new Holder3<Automobile>(new Automobile());          Automobile a = h3.get(); // No cast needed          // h3.set("Not an Automobile"); // Error          // h3.set(1); // Error      } }

Chapter 13: 字串

StringBuilder

• String可以用 "+" 來串連起來，但每次compiler都會產生一個新的StringBuilder物件來處理，效率較差。
• 最好是直接用StringBuilder的append( )跟toString( )來串連字串，效率較高。

public class WhitherStringBuilder {      public String implicit(String[] fields) {          String result = "";          for(int i = 0; i < fields.length; i++)              result += fields[i];          return result;      }      public String explicit(String[] fields) {          StringBuilder result = new StringBuilder();          for(int i = 0; i < fields.length; i++)              result.append(fields[i]);          return result.toString();      } }

Chapter 11: 持有你的物件

Container的列印

• Java容器庫分成兩類，Collection和Map，差別在於每個位置的元素個數。
• Collection：每個位置只能持有一個元素
  • List
    • ArrayList
    • LinkedList (提供的功能較多，random access較慢，在中央位置做插入/刪除較快)
  • Set(元素不得重複)
    • HashSet：使用較複雜方法儲存元素，為取得元素最快速的方法，但元素內沒有順序。
    • TreeSet：元素會照比較結果排序。
    • LinkedHashSet：元素會照加入的順序來排序。
  • Queue
• Map：每個位置持有兩物件，key及value。(下列三種Map的特性與Set類似名稱的特性相同)
  • HashMap
  • TreeMap
  • LinkedHashMap
• 若希望可以不用管是用哪個container，而使用通用的存取方式，則可用iterator來達成。

Chapter 10: 內隱類別

撰寫inner classes

• 若想要在outer class的non-static method之外產生一個inner class物件，須以OuterClassName.InnerClassName的形式指定該物件的型別。

public class Parcel2 {      class Contents {          private int i = 11;          public int value() { return i; }      }      // 一般會在outer class中建立method來產生inner class物件      public Contents contents() {          return new Contents();      }      public static void main(String[] args) {          Parcel2 q = new Parcel2();          // Defining references to inner classes:          Parcel2.Contents c = q.contents();      } }

• outer class又可稱為enclosing class
• inner class可以存取enclosing class的所有成員，就好像inner class自己擁有這些成員一樣。
• non-static的inner class會自動記錄一個reference指向enclosing class的某個物件，後者就是此inner class物件的製造者。也就是一定會先有enclosing class物件才有辦法產生inner class物件。

使用.this及.new

• 若想在inner class中產生指向outer class物件的reference，可以使用OuterClassName.this。

public class DotThis {      void f() { System.out.println("DotThis.f()"); }      public class Inner {          public DotThis outer() {              return DotThis.this;          }      }      public Inner inner() { return new Inner(); }      public static void main(String[] args) {          DotThis dt = new DotThis();          DotThis.Inner dti = dt.inner();          dti.outer().f();      } }

• 若是想用outer class物件來產生inner class物件，可使用.new。

public class DotNew {      public class Inner {}      public static void main(String[] args) {          DotNew dn = new DotNew();          DotNew.Inner dni = dn.new Inner();      } }

位於methods和scopes內的inner class

• 基於兩個理由可能會想這樣做
  • 想實作某個interface，使你可產生並回傳其reference。
  • 希望在解決方案中設計某個class，又不希望此class給外界使用。

public class Parcel5 {      public Destination destination(String s) {          class PDestination implements Destination {              private String label;              private PDestination(String whereTo) {                  label = whereTo;              }              public String readLabel() { return label; }          }          return new PDestination(s);      }      public static void main(String[] args) {          Parcel5 p = new Parcel5();          Destination d = p.destination("Tasmania");      } }

匿名的inner class

public class Parcel7 {      public Contents contents() {          return new Contents() { // Insert a class definition              private int i = 11;              public int value() { return i; }          }; // Semicolon required in this case      }      public static void main(String[] args) {          Parcel7 p = new Parcel7();          Contents c = p.contents();      } }

• 產生某個匿名class的物件，此匿名class是繼承自Contents。
• new回傳的reference會被自動向上轉型為Contents reference。

巢狀類別

• static的inner class被稱為nested class。
• nested class意味著：
  • 生成nested class的物件時不需要outer class的物件了。
  • 無法在nested class的物件中存取outer class的non-static物件。
  • 可擁有static data及nested class。

為什麼需要inner class

• 若你想同時繼承多個抽象或具象的class，必須用inner class來做到。

繼承inner class

• 繼承inner class時，指向outer class物件的reference必須被初始化。

class WithInner {      class Inner {} } public class InheritInner extends WithInner.Inner {      //! InheritInner() {} // Won’t compile      InheritInner(WithInner wi) {          wi.super();      }      public static void main(String[] args) {          WithInner wi = new WithInner();          InheritInner ii = new InheritInner(wi);      } }

Chapter 09: 介面

抽象類別與抽象函式

• 為了建立讓子型別都可用的共同介面，可以讓base class成為一個abstract class。
• 只有宣告而無本體的method稱為abstract method。(相當於C++的pure virtual function)

abstract void f();

• 含有一個或多個abstract method的class需以關鍵字abstract做為此class的飾詞。
• 不能產生abstract class的物件，因為他只是用來表示介面。
• 繼承abstract class的話必須實做所有abstract method才能產生物件，若沒有實作所有abstract method，此class仍然要加abstract做為abstract class。
• 若只是單純不希望某個class被產生出物件，也可以將沒有abstract method的class變為abstract class。

介面

• interface可以想像成是"純粹"的abstract class。
• interface內的data member都預設為public final static。
• interface內的method都只能是宣告，而且預設為public。
• 可以透過繼承來擴充interface，但繼承它的也要是一個interface。
• 只有對interface允許extends後面接一個以上的interface。

interface vs. abstract class

• interface的好處
  • 能被向上轉型到多個base class (多重繼承時)
  • 和abstract class一樣使其無法產生物件
• 若不帶任何函式定義及成員變數，應該優先選擇使用interface。

Chapter 08: 多型

多型 (Polymorphism)

• 又稱為dynamic/late/run-time binding
• 用base class的reference指向其derived class的物件，執行期間才依據物件是哪個class執行其所override的method。

陷阱: fields及static methods

• 多型只用在一般的成員method，對於成員變數及static method則是在compile time根據reference的class做存取。

Polymorphic methods在建構式中的行為

• 建構式中盡量不要呼叫method，除非其為final或是非override的method。呼叫會override的method可能會因為late binding造成問題且難以debug。

Chapter 07: 重複運用Classes

base class的初始化

• Java編譯器會自動在derived class建構式中插入base class建構式的呼叫動作。

• class A{     A() {print("new A");} } class B extends A{     B() {print("new B");}; } public class C extends B{     public C() {print("new C");}     public static void main(String[] args){           C instance = new C();     } } Output => new A new B new C

• 如果沒有在class中定義預設constructor，編譯器會自動產生一個。
• 如果定義了一個(不論是否有帶引數的)constructor，編譯器就不會產生預設constructor。

Name hiding

• 若在derived class中新增overload的method，C++會把base class中同名的method遮蔽掉，但JAVA不會。

複合 vs. 繼承

• 面對複合跟繼承的選擇時，考慮是否需要做"向上轉型"，有需要才選繼承。

關鍵字final

• final data
  • 不能改變的常數
• final method
  • 確保此method在繼承過程中不能被override
  • 允許compiler將此method轉化為inline呼叫
• final class
  • 此class不能被繼承

補充: 重要範例 1 !!

父類別 public class Super {     static String s = "Super=====";     static {  //類別的初始化          System.out.println("instance super class static");     }     {  //類別物件的建立          System.out.println("instance super class");     }     public Super(){  //建構子          System.out.println("into Super constructor");     } }

子類別 public class Sub extends Super{     static String s1 = "Sub1-----";     static String s2 = "Sub2-----";     static {  //類別的初始化          System.out.println("instance sub class static");     }     {  //類別物件的建立          System.out.println("instance sub class");     }     public Sub(){  //建構子          System.out.println("into Sub constructor");     } }

Main類別 public class Main {     public static void main(String[] arg){          Sub sub = new Sub();     } }

執行結果 instance super class static instance sub class static instance super class into Super constructor instance sub class into Sub constructor

補充: 重要範例 2 !!

Main類別 public class Main {     public static void main(String[] arg){          System.out.println(Sub.s);          System.out.println(Sub.s1);     } }

執行結果 instance super class static Super===== //此時Sub類別並不會進行類別的初始化 instance sub class static Sub1----- //此時Sub類別才有進行類別的初始化動作

Chapter 05: 初始化和清理

Cleanup

• 當garbage collector打算開始釋放物件所占的空間時，會先呼叫其finalize()，並且在下一次的garbage collect動作發生時回收該物件所占的空間。
• 觀念：
  • 物件有可能不被garbage collector回收(程式執行到結束中間沒有發生memory不夠)
  • garbage collection並非deconstruction
  • garbage collection只回收memory
• finalize()存在的意義：
  • free以new物件之外的方式配置某個儲存空間(例如呼叫C/C++的native function)
  • termination condition的檢查(協助debug)

Garbage collector的運作方式

• Java從heap配置物件的速度逼近其他語言從stack挖掘空間的速度。
  • C++之類的heap在配置時需要時間去做"搜尋可用空間"之類的大動作。
  • Java heap像是輸送帶，配置物件時，heap指標只是單純的前往還沒配置的下一個區域。
  • 這是因為garbage collection會重新安排heap內的物件，讓它們緊密排列，避免page fault發生。

物件生成的過程(以名為Dog的class為例)

• constructor實際上是static method，所以當Dog物件首次被產生，或是Dog的static member/method首次被存取，JAVA interpreter會找出Dog.class。
• 當Dog.class首次被載入後，它所有的static初始化動作會被執行。
• 從heap上配置Dog物件的空間。
• 把這塊空間清為0，將物件的基本型別成為設成預設值，reference成員設成null。
• 執行各成員在定義處的初始化動作。
• 執行constructor。

static明確初始化

• JAVA允許將多個static初始化動作置於static block中。

public class Spoon {      static int i;      static {          i = 47;      } }

Variable Argument List

public class NewVarArgs {      static void printArray(Object... args) {          for(Object obj : args)              System.out.print(obj + " ");          System.out.println();      }      public static void main(String[] args) {          // Can take individual elements:          printArray(47, 3.14F, 11.11);          printArray("one", "two", "three");          printArray(new A(), new A(), new A());          // Or an array:          printArray((Object[])new Integer[]{ 1, 2, 3, 4 });          printArray(); // Empty list is OK      } } /* Output: (75% match) 47 3.14 11.11 one two three A@1bab50a A@c3c749 A@150bd4d 1 2 3 4

• 可使用省略符號(...)來定義可變引數列，也可以用foreach來做iteration。

Chapter 04: 控制執行

Label

• 可以在iteration述句(for, while..)前放label，可以在巢狀迴圈中讓break跟continue越過一個以上的巢狀level。

  ---

     label1:
     outer-iteration {
         inner-iteration {
             //...
             break; // (1)
             //...
             continue; // (2)
             //...
             continue label1; // (3)
             //...
              break label1; // (4)
         }
     }

• ---

  (3) 是跳到label1的地方並重新進入外層iteration
• (4) 是跳到label1的地方但不再進入iteration

Chapter 02: 萬事萬物皆物件

• 除了基本型別外，Java把所有東西都視為"物件"，但用來操控物件的識別字，實際上是其reference而已。
• 你可以產生一個String reference：

  ---

  String s:

• ---

  但這麼寫只會產生一個reference，而不是實際的物件。

 基本型別

• 基本型別有Wrapper class，如果想在heap內產生代表該型別的物件則可用其wrapper class。例如：

  ---

  Character ch = new Character(‘x’);

  ---

• 所以這類變數直接存放資料值，並置於stack。
• 這一類極小、極簡單的變數若透過new物件的方式置於heap上會顯得效率不彰。
• Java SE5的autoboxing會自動將基礎型別轉成wrapper type：

  ---

   Character ch = ‘x’;

  ---

• 然後將其取回：

  ---

  char c = ch;

  ---

Java中的Array

• Java保證array一定會被初始化，放物件的array每個元素會初始化為null，放基本型別的array則會將memory都清為0。
• Java對array的存取不會超過範圍，但每個array會額外多出一點點的空間，並得在執行期對index做檢查。

Class內基本成員的預設值

• 當class內的成員是基本型別時，Java會保證它有預設值。
  •      boolean => false
  •      char => '\u0000' (null)
  •      byte/short/int/long/float/double => 0