[Algorithm] 平均值計算，避免overflow

Avg(n)=(n-1)/n*Avg(n-1)+data[n]/n

[Algorithm] 如何使用Java 撰寫 libsvm，以XOR為例

　　上一篇介紹如何使用 libsvm，以XOR為例，而這篇要介紹如何使用java撰寫libsvm(以下稱之jlibsvm)，一樣使用XOR做為例子。

　　jlibsvm的概念與上篇使用windows command的相同，只要想辦法把那五大驟轉換成程式碼即可。那我們就按照這五大步驟介紹，以下只針對重要介紹，完整程式請參考LibSVM。

• 步驟一：資料收集 
  
• 步驟二：資料前處理 (將格式轉換成符合訓練模型的格式)
  目標將以下格式轉換成程式碼，
  
  
  0  1:-1  2:-1
  1  1:-1  2:1
  1  1:1  2:-1
  0  1:1  2:1
  
  用來記錄這個的類別為，
  svm_problem {
      int l; //訓練資料筆數，以此例子長度為4
      double[] y; //輸出
      svm_node[][] x; // 輸入
  }
  
  使用方式如下，

  l = 4

  y -> 0 1 1 0 

  x -> [ ] -> (1,-1) (2,-1)

       [ ] -> (1,-1) (2, 1)

       [ ] -> (1, 1) (2,-1)

       [ ] -> (1, 1) (2, 1)
  



• 步驟三：訓練模型
  訓練模型並接模型儲存起來。
  
  
  // 訓練模型
  svm_model model = svm.svm_train(svmProb, svmParm);
  // 儲存SVM參數
  svm.svm_save_model(filepath, model);


• 步驟四：測試模型
  
  //載入SVM參數
  svm_model model = svm.svm_load_model(filepath);
  //輸入Input
  svm_node[] x = svmProb.x[i];
  //輸出Output
  v = svm.svm_predict(model, x);

Reference
[1]碼上會!Java+libSVM分析動態資料(144行)
[2]LibSVM

[Algorithm] 如何使用 libsvm，以XOR為例

libsvm是由台大資工林智仁老師實驗室所開發的強大軟體。但初學者的我，即使看了支持向量機器(Support Vector Machine) | 逍遙文工作室和笨蛋也可以用libsvm。還是搞不懂這東西到底怎麼用。(我連笨蛋都不如Orz....)

　　弄了半天，總算有了小小的了解。記錄一下也分享跟我一樣是新手村的朋友。以我個人而言，搞不懂網路上這些文章到底在幹嘛，主要以下幾個原因：

•  SVM原理不懂 
•  沒有機器學習的Sense 
•  範例太複雜
•  英文有看沒有懂

因此，我使用類神經網路的第一個問題(XOR)來測試SVM。在這之前，先簡單解釋分類演算法不外乎以下幾個步驟：

• 步驟一：資料收集 
• 步驟二：資料前處理 (將格式轉換成符合訓練模型的格式)
• 步驟三：訓練模型
• 步驟四：測試模型
• 步驟五：確認模型是否符合需求，若沒有則回步驟三從新訓練

了解這些步驟後，我們就開始試看看啦。如何下載安裝已有很多資料，這裡就不多說了，不清楚的朋友們可參考 [LibSVM] Support Vector Machine (SVM) 實驗。而我選擇認windows command的方式來操作libsvm，我認為這是最簡單也最方便的方法。( windows path = .\libsvm-3.19\windows。 )


接著就開始照上面的步驟來做測試，

• 步驟一：資料收集
• XOR真值表(利用真值表的四個狀態做為資料做為訓練資料)：
  

  X1	X2	Output
  0	0	0
  0	1	1
  1	0	1
  1	1	0

  
  
•  步驟二：資料前處理
  資料收集完成後，我們就要將資料轉換成libsvm看得懂得格式。
• libsvm format :

  <分類> 0:<屬性> 1:<屬性>... K:<屬性>  

  
  
• 將真值表轉換成libsvm format(檔案名稱 : xor.txt)
  
  0  1:0  2:0 
  1  1:0  2:1
  1  1:1  2:0
  0  1:1  2:1
  
  
• 調整對應值
  
  svm-scale.exe  xor.txt > xor.txt.scale
  
  svm-scale主要目的將資料數值對應至[0,1]或[-1,+1]之間。若打開xor.txt.scale可發現xor.txt轉換成
  
  0  1:-1  2:-1
  1  1:-1  2:1
  1  1:1  2:-1
  0  1:1  2:1


•  步驟三：訓練模型
  做完資料前處理之後，就可以開始訓練模型啦!!!!
  
• 訓練指令
  svm-train xor.txt.scale
  產出：
  xor.txt.scale.model
  
  顯示：
  *
  optimization finished, #iter = 2
  nu = 1.000000
  obj = -2.504710, rho = 0.000000
  nSV = 4, nBSV =4
  Toatal nSV = 4


• 步驟四：測試模型
  終於來到最後階段。到底由SVM模型準不準呢??
  
  先準備測試檔案。
  
• xor-test.txt
  1  1:-1  2:1
  1  1:1  2:-1
  0  1:-1  2:-1
  0  1:1  2:1
  
  
• 測試指令
  
  svm-predict xor-test.txt xor.txt.scale.model xor.res
  產出：
  xor.res
  顯示 :
  Accuracy = 100% <4/4> <classification>

Accuracy = 100%，這表示預測結果非常準，以上是我使用SVM預測XOR的結果。

Reference :
[1] LIBSVM -- A Library for Support Vector Machines
[2] 支持向量機器(Support Vector Machine) | 逍遙文工作室
[3] 笨蛋也可以用libsvm。
[4] [LibSVM] Support Vector Machine (SVM) 實驗。

[Algorithm] P/NP/NP-Complete/NP-Hard 定義

老是忘記這幾個名詞，還是做個筆記一下。

• 時間複雜度
•  在計算機科學中，演算法的時間複雜度是一個函數，用來描述了該演算法的運行時間等級[1]。
  
  例如  :
  void example(int n) {       // execute times
      int i , sum;                   //       1
      for ( i=0; i<n; i++ )       //       n        
      sum += i;                    //        1
  }                                     //   = n + 2 = O(n)
  => O(n) 表示對任何大小為n的輸入，最差只有n的時間即可運行完成
• 多項式複雜度 - O(1)、O(log(n))、O(n^a)
• 非多項式時間複雜度 - O(a^n)、O(n!)

• 問題的等級
• Unsolvable Problem (無解題)
• Intractable Problm (難解題 : O(a^n)以上的問題)
• NP-Problem
• P(Polynomial Time)-Problem

P: 確定多項式時間內可找到解的問題

NP(困難的問題):不確定多項式時間內可找到解的問題， 但有多項式時間被驗證解。(未找到已知的快速解法，但有快速可驗證的解法)

Ex : 81785036517是否否為質數? 不確定81785936517是否為質數，但可以驗證277877是否為81785936517的因子，並且確定可在多項式時間那處理完，故此問題為NP問題。

NP-Hard :不確定多項式時間內可找到解的問題，也不確定有多項式時間被驗證的解。

NP-Complete :　NP-Hard 與 NP問題的交集，即為NP-Complete的問題(參考圖一)。

圖一 : P=NP or P != NP
圖片來源 : 取至wiki

Reference :
[1] Wiki - 時間複雜度
[2] 論P,NP,NP-hard,NP-complete問題
[3] 漫谈算法（三）NP问题