又到了填志願的時間，掐指一算過了好多年。只記得當年我沒有考指考，直接用推甄的，而推的學校也是親戚不知道哪裡弄來的「去年錄取分數表」，然後就不知不覺的過了大學。最近因緣際會下，朋友要我比較一下落點分析的網站，才發現原來現在好多學校都有提供這樣的服務，不禁讓我覺得，要是當年有這樣的工具也許會上更好的科系XD

市面上落點分析工具最麻煩的地方是要註冊或下載，不過現在都已經是雲端時帶了，下載幹嘛呢？讓我話不多說看看2011台大資管落點分析系統-ImWhatIM怎麼操作吧！

▲2011台大資管落點分析系統

這個系統很簡單的分成三個步驟：

第一步：填寫大學指考科目成績
假設我國文67、英文72、數甲50、物理80、化學77，我在有考的科目填上分數，沒考的分數記不要勾，以免被以零分計算影響結果。

▲可以看到「指考神」貼心的提示

第二步：填入學測成績
假設當時我學測時國文12、英文13、數學10、自然14、社會9，則我就按照提示添入分數。

▲「指考神」還會貼心的算出總級分

第三步：輸入驗證碼並按下「開始落點分析」
設置驗證碼的目的是避免大家濫用這樣好的服務，畢竟一個人應該不會輸入太多次成績吧。當輸入完成後就按下「開始落點分析」，馬上就能跑出結果！


結果出來啦！
鏘鏘鏘，跑出的結果會像這個樣子！

▲琳瑯滿目的學校和科系

科系多到眼花嗎？
在網頁的最下端有篩選器，如果家裡只希望念國立學校，可以選擇讓結果只秀出「公立」的校系。另外我覺得「依照顏色顯示」的功能也很貼心，綠色為底的代表填了有點浪費(誤)，建議選擇「保守區」和「最佳落點區」，並搭配幾個非常想念的「可嘗試區」成為志願的選項。

▲非常貼心的多重篩選器

志願與性向
當然落點分析的結果只是告訴我們比較有可能上什麼系，但不代表我們適合念什麼系。在我大學的經驗，也有許多人有轉系的念頭。因此希望身為準大學生生的您，能多跟兄姊、父母或長輩聊聊他們的工作內容，了解自己理想的未來生活，再從理想的生活去推演想要進入的學系。像我當年選擇資管，就是因為資管容易小本創業(不需要投入廠房設備，只要有台電腦就行了)，而現在也正在走向創業之路。

問題與追蹤
有其他問題可以透過網頁上的我要留言連結與管理者進行互動，就我對系上的了解，不管什麼問題他們都會很熱心的回應；另外也可以加入facebook的粉絲專頁進行進一步的互動。祝福你選填志願得心應手：)

繼續閱讀全文　免註冊指考落點分析 (Powered by 台大資管)

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有26 意見

沒想到「碼上會」還會有第二集，標題有點聳動，但在這裡的「動態資料」指的是從資料庫load 出資料(一般libSVM都是標準格式的讀檔案來分析)。此外這篇還涉及處理一個文字探勘(Text Mining)中重要問題 ─ 資料分散(Sparse data)。由於網路上沒有其他實作，所以我想使用以下講解的程式碼，可以讓你加快libSVM的分析效能，也可以提升不少工作效率(不用再輸出多個檔案就能交叉測試)。

▲將libSVM嵌入你的java程式，從資料庫中撈出資料直接訓練

libSVM簡介
這是台大林智仁老師所開發的SVM工具，應該是世界上最好用且最主流的SVM，許多國內外的研究都透過他完成的。其實SVM之所以會成為主流，是因為它的效率較高，而且結果也不錯，甚至有學者認為SVM可以取代類神經網路(林國峰等，2009)。沿襲「碼上會」的精簡風格，廢話就不多說，想更了解這套工具可以參考以下連結：

• libSVM官網：http://www.csie.ntu.edu.tw/~cjlin/libsvm/ (包含多種程式語言工具下載)
• libSVM中文版簡易入門：http://ntu.csie.org/~piaip/svm/svm_tutorial.html (其實講得還算詳細)

大概就這樣吧，想要知道怎麼在Java 中使用，其實可以直接看這篇XD

讓Java 能使用libSVM
為了讓Java 能使用libSVM，必須先下載libSVM的.jar。你可以到官網的這裡下載，也可以點這個連結下載.zip檔案，並解壓縮。解壓縮之後會成為一個資料夾(名稱如libsvm-3.0)，你可以瀏覽到裡面的Java 資料夾，就可以找到libsvm.jar。

讓Java能使用libSVM.jar的方法，可以參考上一集中「來吧！我們來斷詞」的第二張圖，將專案的程式庫「新增外部JAR」，瀏覽到libsvm.jar即可。若在建置專案的時候忘記新增，也可以在Eclipse(我假設你用Eclipse啦，因為我現在用Eclipse開發)左側欄中專案名稱上按右鍵，選擇內容，也可以到達設定的對話視窗。

144行Java 程式「碼上會」
好，以下我假設你會用Eclipse建置專案，並且會新增JAR，並新增一個Class。這裡假設我們的Class叫做「libSVMDemo」。建立好類別後，我們先把可能會用到的參考都先import進程式，如下：

import java.io.IOException;
import java.sql.*;
import java.util.Vector;

import libsvm.*;

由於我們會使用到資料庫，所以要import sql.*;；此外也一定要用到libsvm.*啦！接著，我們要在public class libSVMDemo中插入三個全域變數：

svm_parameter _param;
svm_problem _prob;
String _model_file;

其中，

• svm_parameter：SVM的參數
• svm_problem：之後會儲存要被分析的資料
• _model_file：model檔案的路徑

loadData()：將資料庫的資料轉換成SVM可以解決的問題


這裡我們使用SQLite作為demo的資料庫，其實在Java中，只需使用SqliteJDBC就可以直接增刪改查資料庫，為了順利進行，你可以在這裡下載JDBC的.jar，並請記得如法炮製將該.jar加入專案中(不用import，只要加入專案路徑即可)。如果想要檢視資料，可以使用免安裝的SQLite Administrator。簡述一下本範例中的訓練資料：共5000筆，使用3000個維度，但是每筆只使用兩個維度，而且可能維度還相同(非常的分散)。

這隻程式先讀取資料庫的資料，將讀出之資料轉換成SVM可以解決的問題。由於SVM分成訓練(Training)階段與測試(Testing)階段，通常拿大部分的資料(前4700筆)作訓練，再拿其他沒被訓練過的(後300筆)作測試，了解SVM的效能，因此程式一開始使用參數「is_training」判斷是哪個階段，撈出不同的資料。我們來看程式：

protected void loadData(boolean is_training){
	String limit;
	if(is_training){	//訓練階段
		System.out.print("Loading training data...");
		limit = " WHERE id <= 4700";
	}else{			//測試階段
		System.out.print("Loading testing data...");
		limit = " WHERE id > 4700";
	}
	
	int max_index = 0;	//紀錄資料中最大的維度(用來產生gamma參數)
	_prob = new svm_problem();
	Vector vy = new Vector();
	Vector vx = new Vector();
	
	try{
		Class.forName("org.sqlite.JDBC");		//連接資料庫
		Connection conn = DriverManager.getConnection("jdbc:sqlite:sparseData.s3db");
		Statement stat = conn.createStatement();
		ResultSet rs = stat.executeQuery("SELECT * FROM data"+limit);
		
		while (rs.next()) {
			vy.addElement(rs.getDouble("label"));	//labal為資料的標籤，為-1或+1
							//SVM通常就是解決是好(+1)或壞(-1)的問題
			
			int rdk1 = rs.getInt("rdk1"), rdk2 = rs.getInt("rdk2");
			//讀取兩個維度的資料，這裡只有「有這個維度(true)」與「沒有這個維度(false)」
			//因此兩個欄位只填寫維度的index，例如填寫30，就代表第30維有資料
			//假設rdk1=30，rdk2=2789，則這個node只有這兩個維的值是true，
			//其他2998維(比如第31, 32...維)的值都是false
			if(rdk1 == rdk2){	//兩個維度的index相等，只放一個
				svm_node[] x = new svm_node[1];
				x[0] = new svm_node();
				x[0].index = rdk1;
				x[0].value = 1;
				max_index = Math.max(max_index, rdk1);
				vx.addElement(x);
			}else{
				if(rdk2 < rdk1){	//如果第二個index比第一個小，交換
					rdk1 = rdk2;
					rdk2 = rs.getInt("rdk1");
				}
				
				svm_node[] x = new svm_node[2];		//建立SVM node的陣列
				x[0] = new svm_node();
				x[0].index = rdk1;			//維度的index例如30
				x[0].value = 1;				//有值，為true
				x[1] = new svm_node();
				x[1].index = rdk2;			//維度的index例如2789
				x[1].value = 1;
				max_index = Math.max(max_index, rdk2);	//記下目前用到最大的維度
				vx.addElement(x);			//儲存SVM node的陣列
			}
	    }
	    rs.close();
	    conn.close();
	}catch(Exception e){
		e.printStackTrace();
	}
	
	if(max_index > 0) _param.gamma = 1.0/max_index;		// 1/num_features	
	_prob.l = vy.size();						//svm node的數量
	_prob.x = new svm_node[_prob.l][];
	for(int i=0;i<_prob.l;i++) _prob.x[i] = vx.elementAt(i);	//儲存每個node的向量
	_prob.y = new double[_prob.l]; 
	for(int i=0;i<_prob.l;i++) _prob.y[i] = vy.elementAt(i);	//儲存每個node的label
	
	System.out.println("Done!!");
}

這邊有兩件事需要非常非常鄭重強調：

• 由於資料非常分散，所以我們只儲存「有值」的維度，沒有值得維度連new都沒有。根據筆者的經驗，若參考這篇SVM範例的方式建立SVM node，當資料維度一大，系統記憶體非常容易爆掉，出現java.lang.OutOfMemoryError: Java heap space的例外，就算增加配置給JVM的記憶起，只是跑久一點才爆，會更遺憾XD
• 第二件事是，你會發現我在存入node之前有先對維度比大小，再由小到大插入。這嚴重關係到SVM預測的準確度。如果沒有由小到大插入，SVM一樣會動，但是準確率大概會降低個一半，這點是我測試超久之後才發現的嘔心瀝血之言。

好了，到這裡你已經會把資料庫的資料轉換為SVM的問題，接著的步驟都簡單到不行了！

training()：對SVM問題進行訓練


當資料轉換為SVM問題後，我們只需要簡單的幾個步驟就可以將SVM問題訓練成SVM model，請看程式：

protected void training(){
	loadData(true);	//這邊呼叫loadData()，使用true參數是因為在training階段
			//透過loadData，將資料庫的資料儲存在全域變數_prob裡面
	
	System.out.print("Training...");
	_model_file = "svm_model.txt";	//指定SVM model儲存的檔案名稱
		
	try{
		svm_model model = svm.svm_train(_prob, _param);	//訓練SVM model
		System.out.println("Done!!");
		svm.svm_save_model(_model_file, model);		//將訓練結果寫入檔案
	}catch(Exception e){
		e.printStackTrace();
	}
}

到這裡已經建立預測的model了，你是否覺得你的智商被汙辱了呢？

testing()：對剩下的資料進行測試

當訓練完之後，我們必須對其他資料進行測試，看看這個model預測的準確率。請看以下程式：

protected void testing(){
	loadData(false);	//讀取剩下的300分資料，轉換成SVM問題(存在_prob裡)
	
	svm_model model;
	int correct = 0, total = 0;
	try {
		model = svm.svm_load_model(_model_file);	//載入model
		
		for(int i=0;i<_prob.l;i++){	//對problem 裡的每個SVM node
			double v;
			svm_node[] x = _prob.x[i];	//取出svm node
			v = svm.svm_predict(model, x);	//把node餵給預測器
				//這時預測器會依照model與node內的向量資訊，產生預測的數值(-1或1)
			total++;
			if(v == _prob.y[i]) correct++;	//如果跟正確答案一樣，則正確數加一
		}
		
		double accuracy = (double)correct/total*100;
		System.out.println("Accuracy = "+accuracy+"% ("+correct+"/"+total+")");
	} catch (IOException e) {
		e.printStackTrace();
	}
}

到這裡，其實SVM的部分已經搞定了，你應該已經躍躍欲試的想拿來預測了吧(?)，不過還請看完...

libSVMDemo()建構子：產生參數與呼叫訓練/測試方法

直接看程式吧：

libSVMdemo(){
	// default values
	_param = new svm_parameter();
	
	_param.svm_type = svm_parameter.C_SVC;
	_param.kernel_type = svm_parameter.LINEAR;
	_param.degree = 3;
	_param.gamma = 0;		// 1/num_features
	_param.coef0 = 0;
	_param.nu = 0.5;
	_param.cache_size = 100;
	_param.C = 1;
	_param.eps = 1e-3;
	_param.p = 0.1;
	_param.shrinking = 1;
	_param.probability = 0;
	_param.nr_weight = 0;
	_param.weight_label = new int[0];
	_param.weight = new double[0];
	
	training();
	testing();
}

雖然這部分簡單到爆炸，但是我還是要囉嗦兩句：

• 要注意的是kernel_type參數，這個跟預測的準確率有極高的相關性，一般一分為二我們會使用Linear的Kernel
• 另外一個可以試的參數是C，在這裡是1，可以把他往下調，看看結果準確率是否有提高。

附件下載：libSVMdemo.zip (解開為Eclipse專案資料夾，裡面包含資料庫、該有的jar)

結語

跟上集「碼上會」一樣，這篇也只是協助你快速上手libSVM，並簡單介紹幾個我遇到的問題的解決方法，希望對未來研究的後輩能有所貢獻。對你有幫助或有任何問題指教，也請不吝惜告知，謝謝！

繼續閱讀全文　碼上會！Java+libSVM 分析動態資料 (144行)

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有7 意見

好，我承認標題下得有點好笑，而且也很意外寫這種實作的文章(我早就往理論派轉型了)。總之照著這篇文章的步驟，你可以使用java 將一串正體(繁體)中文的字串依照詞彙切開，以方便進行中文文字探勘(Text Mining)等計算詞頻的工作。

▲mmseg4j中文斷詞結果，可以看到它把「處理」、「文章」等詞分割出來

首先呢，為了簡化開發，程式都在Eclipse 上開發，以下用簡單兩句話說明Eclipse 如何安裝：

• 到Java網站，下載並安裝JRE (請選擇合適的作業系統)
• 到Eclipse官網，下載Eclipse Classic 版本，將之解壓縮之後，執行資料夾中的Eclipse.exe ，就可以用它來寫Java 程式了

簡單介紹MMSeg 與mmseg4j
mmseg4j 是採用蔡志浩先生在2000 年發表的一個中文分詞演算法 ─ MMSeg，它使用兩套演算法與四個模糊解析規則，據稱能達到98.41% 中文斷詞準確率(理論請參考MMSeg官網)。這樣的準確率已經近似於大陸中科院的ICTCLAS，973計畫專家組評測第一名的98.5%，此外mmseg4j在斷詞速度表現良好，高達1900kb/s(Simple版本)，根據5樓網友實測表示比庖丁(Paoding)還快。

此外可喜可賀的是，mmseg4j詞庫採用utf-8編碼(不像ICTCLAS使用GB)而且可以自訂，因此只要替換詞庫就可以用來將優美的正體中文進行斷詞，以下來稍微介紹一下詞庫。mmseg4j 預設使用sogou 詞庫(去除無意義詞)，並合併rmmseg (Ruby中文斷詞套件)的詞庫，共14多萬詞。詞庫放在jar裡面，若使用WinRAR等軟體，將下載解開的mmseg4j裡面的mmseg4j-all-X.X.X-with-dic.jar 再解開，裡面的data 資料夾就是詞庫檔預設的位置。

• chars.dic：單一字和對應的頻率，提供complex模式使用。
• units.dic：單位詞，如：分、秒、年。主要是在數位後面的單位資訊切分好，不與words.dic中的詞有混淆。
• words.dic：核心的詞庫檔，一行一詞，不需要其它任何資料，採utf-8編碼。

若要自訂辭典，檔案名必需是 “words” 為首碼和“.dic”為副檔名，例如wordsXXX.dic。然後我們可以把這個些自訂的詞庫集中在某個資料夾，並在程式中設定讀取這些詞庫檔(稍後會示範)，也可以把這樣的純文字文件用WinRAR壓縮回mmseg4j-all-X.X.X-with-dic.jar 的data 資料夾中。

官網(簡體)下載mmseg4j：mmseg4j (請選擇最新的zip檔案，名稱會如「mmseg4j-1.8.3.zip」)

下載mmseg4j 正體(繁體)中文詞庫
以下詞庫是筆者透過程式工具將原本的詞庫轉為正體字，以方便台港使用者研究學習，歡迎下載分享，但請註明來源:)

• units.dic、words.dic 正體版
• mmseg4j-all-1.8.2-with-dic.jar 正體版，我把辭典包在這裡面，所以不介意也可以直接用這個jar(之後我demo的程式也是使用這個jar)

來吧！我們來斷詞
當然不免俗的啟動Eclipse之後，我們必須先建立一個專案。檔案 > 新增 > Java專案

▲名稱取作SegChinese

▲下一步到Java 設定的地方，選擇新增外部JAR，然後瀏覽到剛剛下載來的mmseg4j-all-X.X.X-with-dic.jar，新增後按下完成。接著展開左邊專案目錄，在src上按右鍵，選擇新增類別，取個類別名稱，在這裡我還是取為「SegChinese」。

55行java 程式「碼上會」
我們要import這些東西，如下：

import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;

import com.chenlb.mmseg4j.ComplexSeg;
import com.chenlb.mmseg4j.Dictionary;
import com.chenlb.mmseg4j.MMSeg;
import com.chenlb.mmseg4j.Seg;
import com.chenlb.mmseg4j.Word;

值得注意的是import com.chenlb.mmseg4j.ComplexSeg代表使用Complex 版本的斷詞(包含四個模糊規則)；若要使用簡單版本，請換成import com.chenlb.mmseg4j.SimpleSeg;。

接下來，我們在class裡面宣告一個字典型態的變數dic(儲存詞庫)，並建立建構子與設定一些程式資訊，如下：

protected Dictionary dic;
	
public SegChinese() {
	System.setProperty("mmseg.dic.path", "./src/SegChinese/data");	//這裡可以指定自訂詞庫
	dic = Dictionary.getInstance();
}

protected Seg getSeg() {
	return new ComplexSeg(dic);
}

Seg方法可以指定要使用的分詞器，在這邊使用Complex(複雜版的)，並將字典及放入分詞器中。這裡一定要提一下，自訂的字典可以藉由 System.setProperty("mmseg.dic.path", "路徑"); 來指定，其中路徑若是相對路徑的話，是相對於專案資料夾的目錄，在上面的例子中，我故意將字典資料夾放在專案資料夾中的src/SegChinese裡的data資料夾中，我們可以在data資料夾中放入多個字典檔，就可以使用多個字典。

再來我們要建構程式的斷詞核心部分，如下：

public String segWords(String txt, String wordSpilt) throws IOException {
	Reader input = new StringReader(txt);
	StringBuilder sb = new StringBuilder();
	Seg seg = getSeg();
	MMSeg mmSeg = new MMSeg(input, seg);
	Word word = null;
	boolean first = true;
	while((word=mmSeg.next())!=null) {
		if(!first) {
			sb.append(wordSpilt);
		}
		String w = word.getString();
		sb.append(w);
		first = false;		
	}
	return sb.toString();
}

這裡我們傳入一個字串與一個希望用來作為分隔的符號，接著使用MMSeg進行分詞，每個詞可以用.next()取得，最後把它變為字串回傳。

最後我們建立一個run 方法，用來傳入測試段詞的文字。以及main 方法以測試程式執行，如下：

protected void run(String[] args) throws IOException {
	String txt = "這行文字是要被中文斷詞處理的文章，可以從執行結果看斷詞是否成功 莊圓大師";
	
	if(args.length > 0) {
		txt = args[0];
	}
	
	System.out.println(segWords(txt, " | "));
}

public static void main(String[] args) throws IOException {		
	new SegChinese().run(args);
}

在run中我傳入直線(|)作為分隔符號，以上短短55行就完成了中文斷詞，輸出結果頁首所示。我把這份java 檔附在文末，也歡迎下載測試。

附件下載：SegChinese.java

結語

在這裡我要感謝前輩Deduce的提點，讓我能花相對少的摸索找到這套工具。當然這只是一篇讓讀者很快了解如何使用mmseg4j的小品文，所以只精簡的介紹了最基本以及常用的功能。我在java/text mining上的確是晚輩，所以若有撰寫不當也請各界多多包含與指教。

繼續閱讀全文　碼上會！ mmseg4j 中文斷詞java 實作 (55行)

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有7 意見

看完這篇文章，你會對機器學習最入門的概念─「感知學習演算法」有基本的認知。因為筆者數學並不好，為了寫這篇，我花了大約30小時，看了10多個版本的教學(n次)，在成大數學的高手歐民同學的指導下，站在好懂的角度撰寫，希望不會令你感到失望 :)

感知器是幹麻用的？
用來產生判斷結果！會經由多個輸入的數據，透過運算產生一個非黑即白的結果，用途相當廣泛。例如透過收入、負債的數據，協助銀行判斷顧客是否可以核辦信用卡(可發/不可發)、或是可以找出潛在消費者(潛在/非潛在)、判斷股票未來的走勢(漲/跌)等等。

感知器的靈感是來自生物的神經元(下圖)，神經元從樹狀突接收不同來源的訊號，其中有些來源的刺激具正向效果、有些來源則是抑制效果，經過加總計算後，如果結果達到該神經的門檻值，則會將訊號從軸索末端傳出；或沒達到門檻，則不傳出訊號(在此為了講解方便，將訊號簡化為有與無，實際上神經元有很多種，也有些會依照加總輸出不同強度的訊號，但不在今日討論範圍內)。

▲神經元(Neurons)，主要構造有樹狀突(Dendrites)、細胞體(Cell Body)與軸索(Axon)，圖片來自UCODE資優密碼

如何透過輸入進行分類？
在我們了解感知器的基本功能後，現在要進一步探討，輸入的數據與分類結果的關係。假設我們腦中有一顆功能是判斷一個男人可不可以嫁的神經元，它只有兩根樹狀突，一根偵測這男人專情程度、另一根偵測他的上進心。接著你得到了50個老婆覺得婚姻幸不幸福的資料，其中紅色的老婆覺得婚姻幸福美滿，藍色的則是有家庭問題或離婚的，如下所示：

 
▲描述這些女人他們老公的資訊，專情程度用「心上人數」來代表，心上人越多則越不專情；上進心用「上進時數」表示，時數越高越上進

從圖片中直觀的可以發現，心上人數越少且上進時數越多的老公，越能帶給家庭幸福(不過如果沒有這個統計結果，我們很難證明有這樣的關係存在)。接下來也就是感知器最神奇的地方，今天的重點。感知器從心上人數、上進時數等資訊，經過一些變數的調整(調整影響力的強弱)，產生可不可以嫁的答案。這些答案是透過資料訓練出來的，所以沒有經過資料訓練的感知器不會有分類功能，在這裡必須給他先讀過這份「老婆幸福報告書」，才能從結果中歸納出衡量的準則(「心上人數」要少且「上進時數」高才是可以嫁的男人)。

因此我們的目標是，透過這些這份報告書的訓練的資料，建立一個公式，讓未來只要知道某男人的「心上人數」與「上進時數」等資訊，就能馬上判斷這男人可不可以嫁：

(心上人數 * w1) + (上進時數 * w2) = 一個數字
若這數字大於某個值，就表示可以嫁

如何找到這個公式？
接下來問題會變得有點數學，因為我們必須使用數學的方式找到合適的影響力(w1與w2)，使公式產生合理的結果。我們再看看手邊有什麼資訊：

• 50個男配偶的心上人數、上進時數資料(整堆用x表示)。x裡面包含了x1~x50等50筆配偶資料，且每筆配偶資料又包含「心上人數」、「上進時數」兩個數值，因此可以把x1~x50都當作50個不同的向量→(心上人數, 上進時數)
• 我們還必須假設一組數據，代表心上人數、上進時數分別的影響力，這個影響力會與每個男配偶資料相乘(作向量內積)，幫男配偶打一個分數。在這裡我們用w代表這組數據，其中包含w1的心上人數與w2的上進時數。例如w = (-16, 12)，則第20號男人x20有1.2個心上人與7小時的上進，經過相乘後分數為64.8 = 1.2 * (–16)+ 7 * 12，這樣的乘法就是所謂的向量內積。
• 男配偶的老婆幸福與否(只有幸福/不幸福兩種選項)，這個函數我們取名為sign()。輸入的的是某個男人的分數(例如64.8)，輸出的是-1(代表不幸福)或+1(代表幸福)。

好，大概就這樣，不過一開始，我們不會知道w這組影響力的值，必須要透過既有的幸福/不幸福資料，去調整w的內容，所以接下來進入到最核心的部分。起初，我們將w的值設定為(1,1)，並假設sign()分數大於60則為「可以嫁」，如此開始檢查這樣的w是否可以把第一個男人正確歸類。我們將w與x1作向量內積並帶入sign()中，假設得到+1(可以嫁)，我們再將這樣的結果與統計結果對應，看看一號男人是否真的可以嫁；假設結果也是可以的，於是我們用這組影響力去檢查2號男人。

如果發現2號男人sign()的答案是可以嫁，但實際上(統計中)二號男人不可以嫁，我們就要進行修正(讓2號男變得不可以嫁)。修正的方法如下：

新的w = 舊的w + 2號男人實際上可不可以嫁 * 2號男人的向量

其中，

• 2號男人實際上可不可以嫁：統計的結果，可嫁為+1，不能嫁為-1，2號男人在這裡的值為-1
• 2號男人的向量：(2號男人的心上人數, 2號男人的上進時數)

如此因為新的w加上得負的2號男人向量，可以使2號男人的分數變低，接著就這樣依序檢查3~50號男人。如果存在一條可以分隔可嫁/不可嫁男人的線，Novikoff(1962)證明用這樣的演算法可以在有限次數的反覆計算後得到答案。

結語
感知器其實是類神經網路的基礎，透過感知器可以使電腦在已知的資料中找到規則，並套用到未知的相關資料，以達到預測的效果。雖然在這裡只介紹結果非黑即白的基本感知器模型，不過它已經可以用來解決許多大型的應用問題。但值得注意的是，不是所有的問題都適合用機器學習來解決，例如許多已知可以套用公式的科學領域。

▲歐民大大畫了一大堆圖讓我了解sign()與實際結果的關係，以及分界線到底長什麼樣子

老實說這篇文章真的要感謝歐民大大的相助，因為光憑我一個人的能力我想我很難了解這些資料的內容。當然如果有不正確之處也歡迎各界指教，我寫的目的是在弄懂之後能幫助其他像我曾經一樣的人，不是要造成他們的誤解。

繼續閱讀全文　感知學習演算法(Perceptron Learning Algorithm)白話說明

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有11 意見

明天(9/13)即將開學，讓我們來回顧一下這個暑假吧！整個暑假近三個月的時間(6/24~7/12)，大致上可以分成三個部分。前半段以資種生活為主，令人流連的南京海外參訪、招生專案以及中間的許多小活動；後半段以政大生活為中心，包括大和國的畢業旅行、新生迎新共識營等等。至於第三個部分，是一直貫串的創業與家庭生活，我認為是我的主軸，雖然創業進度大大落後，讓人不堪回顧放假前訂的計畫(說的大話)，但我想累積的這些知識，與自我學習的態度，仍是相當可觀的收穫！

暑期作息表
七月十八日，老楊的研討會論文告一段落(deadline:7/16)，我花了兩天的時間，安排暑假的作息，如下表：

▲ FUNction's 2010 年暑期作息表

規定自己如果沒做到就扣錢，不少內行人問我扣錢要扣到哪去，我說扣掉的錢會統一放著，變成只能用來吃飯，不能玩樂(如看電影、唱歌…)的吃飯金。實行兩個月下來，吃飯金已經高達了2300 元了(今天結算，也停止適用了)！不過還是有不少遏阻自己怠惰的效果，也讓自己暑假的作息比照上班族，控制了應有的工作效率。

資種生活
我想最值得一提的莫過於海外參訪了！這應該是我第一次離開家人這麼久、這麼遠的旅行(羞)。但我覺得與其說是與南京大學、東南大學的學生交流，不如說是與資種菁英們的交心時間。我想問，有多少人現在還繼續跟那些大陸人保持聯絡(迷之音：被藍襯衫糾纏除外XD)？但是，經過了這幾天的交心，我看見了如家人般親愛的種子們，我樂意為他們爆肝，在他們最需要我的時候；我看見了可以與我同行的人、與我一起冒險的人，可以期待在彩虹盡頭相遇的人。

▲ 南京海外參訪前香港機場的合照(我是左一)，後面的告示牌剛好寫著"Nanjing Boarding Soon"

▲ 場勘勘到烏來去了(我又是左一XD)，那天跟芳芳(後排中)一路上都在開心的聊天

▲ 資種結業(我還是左ㄧ啊 = =")，照片中間的「女士」為電腦公會的總幹事。

除了海外參訪難忘的經驗(興奮狂走的百腦匯、說謊不打草稿的Texi 之旅、有船有書法的玄武湖、好吃好shopping 的獅子橋、中山陵、像捉迷藏的夫子廟、小故宮)，場勘變成爬山玩水也十分令人回味。還有畢典難忘又感人的場景，招生的點點滴滴(ex. 打電話排班、到國父紀念館發傳單、版宣貼海報等等)，以及暑假尾端的資種面試服務+慶生，都有許許多多講不完的故事。而資種生涯也在八屆名單公布後告一段落了，往後的日子將以校友的身分成為新種子的陽光或空氣，繼續編織那永遠鮮豔的一年故事。

政大生活
延續了5/19的餞別與5/28的迎新茶會，暑假的畢旅與新生共識營對我來說特別有意義。共識營中我擔任小隊輔(另一個隊輔是同為輔大出身的葉又誠)，不過在我們的小隊6個成員中，有2個是我們實驗室，2個是輔大的，3個是政大原生，1個是補高點的(當然有幾個人分飾多角)，對我來說都很有親切感。我覺得他們是群懂事的孩子，當然，最後專案在他們的耐心與創意下，得到了第二名的好成績，比去年的我們大大進步了一名之多啊XD

▲ 共識營晚上的烤肉(我在後排右二)，右一為又誠。到了晚上由於2個孩子有事，所以我們可以吃得特別飽

▲ 畢旅回國後所上同學的大合照(我在後排右一)，大家都提了大包小包的紀念品與滿滿的共同記憶

去京都、神戶與大阪的畢旅當然一定要提，從看似都一樣的寺廟、開人眼界的環球影城show到每天lab定的目標(Target)都是嶄新的體驗。由於這次是併團的(本所提供10名男丁+4朵所花，師大美術提供10個文藝美女，文化企管提供4人組)，所以成員相當多元，也激出了不同的火花。在日本的這段期間大家都顯露本性，是個真正認識彼此的好機會。也因為多了許多相處時間，我覺得跟Demon 他們也變得比以前熟(而不是之前的嘴砲居多XD)，還無形之中培養了許多寶貴的人脈。我想，畢旅對我來說也是個結束點吧，接下來又要進入新的環境了，但仍與大家一起加油著！

創業之路與小小兼差
這肯定是個嚴肅的話題，連國旗歌都說「創業維艱」了！除了本質的困難，外在的誘因也不少。七月的時候，一個禮拜內接到TSMC 與Microsoft 希望我投履歷的邀請，TSMC 的工程師據了解還是看了我Blog 之後寫信給我的(所以我說沒事寫寫Blog 也會有前途的)，不過我仍然沒動搖。因為我知道我要的是什麼，而且正在朝這個方向努力。今年，一定會開公司。我的回應(精簡後)：我計畫開公司，期盼未來業務上的合作機會。

 
▲ TSMC 的來信(我已經把敏感的字眼都蓋掉了，若有侵權煩請告知，謝謝！)，我Blog 曾名叫"FUNction’s TechNotes"

我常說「我致力於將興趣、創業與研究結合」，所以暑假這段期間，雖然還沒找到指導教授，但我就充當自己的老闆(學業、課業上皆是)。我認為創業與開公司不同，Facebook是創業、Google是創業、微軟是創業，但蔣友柏不是創業(雖然他滿嘴掛著自己是創業家)，因為他充其量只是開間設計公司，每間新公司當然都有它的創新與利基，但是真正的創業是創造一個生態體系，建立新的價值鏈(不只我這麼認為，思華兄也這樣說阿)。總之自己當老闆不是創業，不然每個賣雞排的人都可以說自己是創業家，考慮要不要去康熙或大學生了沒接通告。

所以，創業除了要有點子外，還必須有強大的知識作後盾，這也是整個暑假我花許多時間累積的。我每個禮拜平均看兩篇論文，自己跟自己meeting，作投影片、寫筆記(不是每篇)；每天早上訂當天的目標，並努力達成(當然也有讓自己失望的時候)，雖然現在進度嚴重延後，但我的心底是踏實的。而我也在看論文後想到了一些獨創的text mining 技術，雖然尚未驗證完成，但我相信這段時間的努力對未來事業將會非常有價值！經過昨晚的討論，我們決定要自掏腰包先買機器建立Hadoop 的斷詞環境，以便往後的工作進行。

▲ 我的工作環境，左邊的螢幕看論文，較大的螢幕整理筆記、搜尋或查字典

另一個比較特別的經驗，是今年與國內知名補習班合作解MIS 的研究所考題(並出書)，配合高考SA 助教、寫資管相關刊物、書序等等。但是這實際上是吃力不討好的工作，我這些努力除了佛心來著希望幫助更多的考生之外(今年前10的資管所都是我很用心解的，11月出版的MIS 歷屆試題真的值得收藏阿)，也希望能跟補教菁英有更多的接觸，發展更多元的人生。

家庭生活
這絕對是最輕鬆的部分，繼去年我規畫的家庭澎湖四日遊後，今年換老弟規劃墾丁三日遊，老實說墾丁順利很多很多！這次在墾丁體驗了畢生第一次的拖曳傘、潛水、飆沙、人妖秀等難忘的活動，傍著藍天碧海，著實令人心曠神怡(人妖秀除外XD)。

▲ 第一次玩拖曳傘，看起來有點懼怕XD (但其實上面是很悠閒的!!!)

▲ 第一次潛水(我是左一)，我獨創的蚌殼式抓魚法，將魚餌夾在手跟，成功的抓到了5隻熱帶魚(但是抓到之後就放掉了，我是很有愛心的)

▲ 貌似墾丁豔遇的人妖秀(我是左二)，實際上讓人很不舒服阿！

結語
寫這些無非是提供未來的自己找回初衷的線索，人在不斷追逐中往往會迷失，相信未來的我看到這篇文章會想起這個有骨氣的夏天與一群共同奮戰的朋友。另一個目標是切實檢視這三個月的成長，歲月不待人，三個月可以很充實，也可以虛晃即逝，至此為止，我是問心無愧的。當然暑假中還有發生許多大事、小事，愉快、不愉快，不過不管如何，這些事也讓我也得到了許多的成長。用我七月的銘言共勉之作結吧：「心靈的新陳代謝越快越好，只要慢得足以記取教訓就行了！」

繼續閱讀全文　2010 暑假生活總回顧

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有4 意見

這依然是一篇逐字翻譯的文章，需要注意的是第四節「評估」我沒有完全翻完，因為我已經在第三節「演算法」找到我想看的東西了，而第四節主要就有點老王賣瓜的比較與其他分段方法的優越性，因此我只翻譯了第四節的結論，有興趣的讀者可以閱讀原文。本文分段完全依照原文所訂，對照起來應該相當容易，末段「心得」為我的見解，也一併與你分享。當然，翻譯的目的依然是讓中文為母語的讀者能快速掌握這些知識，以利後進學者的研究。

 
▲研究苦悶可以到郊外走走，看見藍天白雲和蔚藍的大海，必能使人心曠神怡(圖為筆者6:40 在墾丁南灣飯店所攝)

原文：Choi, Freddy Y. Y. 2000. Advances in domain independent linear text segmentation. In Proceedings of the Sixth Applied Natural Language Conference (ANLP-00) and the First Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-00), pages 26–33.

摘要
本文描述一個線性文件分段的方法，比Reyner 在1998年提出的state-of-the-art 精準兩倍、快七倍。我們使用文內排名(rank in the local context)取代跨句相似度(Inter-sentence similarity)；使用分裂群集法(divisive clustering)偵測邊界的位置。

一、介紹
一般的長篇文件通常都會包含多個主題或相同主題的不同觀點，線性文件分段的宗旨是探索文件的主題邊界。資訊檢索(information retrieval)、摘要(summarization)、文件理解(text understanding)、回指解析(anaphora resolution)、語言塑模(language modelling)與改進視障的文件導航都會使用到這個程序。

本文聚焦在與領域無關的書面文件分段方法，我們提出了一個基於Reynar 先前研究的新演算法。最大的區別在相似度矩陣(similarity matrix)，我們使用排名體系(ranking scheme)與餘弦相似度法(similarity measure)。我們希望短文件段落的相似度在統計上是顯著的，使我們在群集時只需依照它們的順序或排名。

二、背景
既有的研究屬於詞彙性銜接(lexical cohesion)法或多來源法(multi-source methods)這一兩個類別(Yaari, 1997)。研究的先驅是1976年的Halliday 與Hasan，他們提出有相似字彙的文件段落可能是凝聚的主題段落(coherent topic segment)的部分，實作偵測凝聚(coherent)的方法有字根(word stem)重複、內容向量(context vectors)、實體重複(entity repetition)、語義相似度(semantic similarity)、文字距離模型(word distance model) 與文字頻率模型(word frequency model)等；尋找主題邊界的方法包含滑動視窗(sliding window)詞彙鏈(lexical chains)、動態程式規劃(dynamic programming)、叢集聚合(agglomerative clustering) 與分裂群集(Reynar, 1994)。為了加強資訊檢索，在群集中的書面文件分段通常使用詞彙性銜接法。

多來源法結合詞彙性銜接與其他主題改變的指標，例如提示語(cue phrases)、韻律特徵(prosodic features)、參照(reference)、語法或詞彙吸引力、使用決策樹與機率模型等。這個領域的研究由「主題偵測追蹤(TDT)」發起，聚焦在錄製展現格式與規律的提示可以精準切割的口語文件與廣播新聞事件的分段。

三、演算法
我們的分段演算法以一串標計化語句作為輸入，使用1994年Grefenstette 與Tapanainen 提出的標記器、句子界限消歧義演算法或Reynar 等在1997年的EAGLE 可以轉換文字文件成為可接受的輸入格式。

(一) 相似度法(Similarity measure)
使用簡單的正規表達式與停用字移除每句中的標點符號非資訊文字(uninformative words)，接著對剩下的標記(token)以1980年Porter 提出的詞幹(stemming)演算法取得字根。為每句建立字根頻率字典(dictionary of word stem frequencies)，代表頻率計數的向量。

令f_i,j代表文字j在句子i中的頻率，句子x 與y 的相似度使用餘弦法計算如(等式1)。對每句使用這樣的方法產生相似度矩陣。

(等式1)

相似度矩陣1的例子如(圖1)，明亮部分代表相似度值高。左下角與右上角分別為第一句與最後一句的自我相似度。值得注意的是矩陣是沿著對角線對稱的且包含明亮的方型區域，這些區域代表凝聚的文件段落。

▲圖1：相似度矩陣1的例子

(二) 排名(Ranking)
對短篇的文件段落，sim(x, y)的絕對值是不可靠的。除非文件區段(分母)很大，因為額外的常見字(分子)會造成相似度sim(x, y)不成比例的增加。由於在一般的情況下，文件段落每個區段小於100 個資訊性的標記，因此只能使用公制(metric)來估計句子間相似度相似度的順序，例如a 比c 相似b。

此外，語言使用變化貫串整份文件。舉例而言，概觀的段落比特定主題的段落凝聚度低。因此，直接比較相似度矩陣不同區域的相似度值並不恰當。

在非參數統計分析中，當值性的行為相似但絕對量不可靠時，我們比較資料集的排名。在此展示一個改編自1992年O’Neil 與Denos 提出的排名體系。

在相似度矩陣以本地區域內(local region)的排名取代每個值，排名是鄰近元素中相似度較低的數值。以下展示一個使用3 × 3 排名遮罩與輸出範圍{0, 8}的圖片排名(image ranking)的例子(圖2)。在文件分段的實務上，我們使用11×11 的排名遮罩。為了避免正規化問題(考慮到排名遮罩超過圖片的情況)，輸出以r 率(等式2)表示。

▲圖2：圖片排名操作的例子。

(等式2)

為了展現圖片排名的效果，程序將套用(圖1)的矩陣以產生(圖3)，值得注意的是我們使圖片的對比更加明顯。(圖4)展現我們的排名體系中更不易察覺的效果。r(x)是f(x) 的排名(使用1 × 11 的遮罩)、是個有衰退平均數(decaying mean)、震幅和頻率的正弦波(等式3)。

▲圖3：排名後圖1的矩陣

(等式3)

▲圖4：我們的排名體系中更不易察覺的效果

(三) 群集(Clustering)
最後階段找出主題界線的位置，使用Reynar 的最大化演算法(maximisation algorithm)。文件段落由兩個句子i 與j 所定義(包含)，它沿著排名矩陣的對角線以一個方形的區域表示。設s_i,j 代表段落中排名數值的總和，內部的區域是a_i,j = (j – i + 1)²。B = {b₁, …, b_m} 是m個凝聚文件段落的清單。s_k 與a_k 指的是B 中段落k 的排名和區域的總和。D 是B 內部的密度(等式4)。

(等式4)

為了初始化程序，整個文件被放在B 中視為一個凝聚的文件段落。每個處理的步驟切割B 中的一個段落，切割點(split point)使D 達到最大值，是潛在的邊界。(圖5)展示實施的例子。

▲圖5：分裂群集(divisive clustering)演算法的實施例子

段落的數量m 是自動產生的，D⁽ⁿ⁾是n 個段落的內部密集度，斜率(gradient)是δD⁽ⁿ⁾ = D⁽ⁿ⁾ - D^(n-1)。當文件有b 個潛在的界限，則分裂群集產生{D⁽¹⁾,…, D^(b+1)} 與{δD⁽²⁾,…, δD^(b+1)} 的b 個步驟(圖6、圖7)。在δD 中極大的化簡促使獲得最佳群集(optimal clustering)，見(圖7)n = 10 時。令μ 代表δD⁽ⁿ⁾的平均數、v 代表變異數，n ∈ {2, …, b + 1}。套用δD的門檻值μ + c × √̅v 得到m (實務中c = 1.2 表現較好)。

▲圖6：所有層級段落的內部密度

▲圖7：使用斜率找到最佳的段落

(四) 速度優化
每個階段的執行時間由s_k的計算過程所支配。由於s_{i, j}是常數，我們的演算法藉由先計算所有的值來改善效能。程序從主對角線(main diagonal)開始沿著對角線走向角落求值，這樣的方法複雜度big O 為3/2n²。令r_{i, j}參考排名矩陣R 的排名值與排名矩陣的加總S。若R 為n × n ，使用三個步驟計算S (等式5)。(圖8)展示程序使用(圖5)排名矩陣的計算結果。

(等式5)

▲圖8：透過計算s_{i, j}促進效能

四、評估 (按：由於評估分成六個步驟，有點冗長，故直接以評估的總結帶過)
實驗結果(表8)展示我們的C99 演算法比既有的演算法精確，精確性高兩倍且速度快七倍(C99_(b)與R98比較)。如果不管段落的精確性，H94是效能最佳的演算法(線性)，C99、K98 與R98 是多項式時間的演算法。我們的結果透過t 檢定與KS 檢定證實其重要性

▲表8：我們實驗結果的摘要

五、結論與未來工作
分段的演算法有兩個關鍵的元素，群集策略與相似度方法。我們的結果展示分裂群集(R98)在找出主題界限上，比滑動視窗與詞彙鏈(K98)更為精確。

驗證四個相似度方法後，餘弦係數(cosine cofficient)(R98_{(s, cos)})與點密集度(dot density)法(R98_{(m, dot)})得到相似的結果。我們基於語義(semantic)方法(R98_{(m, sa)})的促動擴散(spread activation)理論改善精確度。這樣確定即使Kozima 的實作計算成本高，他可以產出較精確的分段結果。

最大的改善是由於我們線性了餘弦係數的排名體系。實驗顯示當資料不足時，餘弦法的值性行為比真實的數值可靠。

即使我們的評量體系對這個比較性研究而言是充足的，但未來的研究需要更大範圍的、任務獨立的基準點(benchmark)。使用TDT文集(corpus)比較C99與1999年Beeferman 提出的多來源法(multi-source method)一定很有趣。我們也想要開發一個線性時間與多來源版本的演算法。

心得
話說剛剛念一念就睡著了，在夢裡我跟亞霖討論最近的研究，聽到他也在做主題分段，高興了一下，醒來猜發現只是一場夢。不過很開心得地方是在夢裡有討論出一點心得，看來多討論對研究還是有幫助的，不要老是跟自己meeting 了。

基本上這篇文章內容很紮實，看完很有收穫。但是從我的理解，本文主要的貢獻是提升的文件分段的效率，在精準度的突破著墨較少，也是較為可惜的地方。本文使用句子的相似度製作相似度矩陣，從矩陣中切割出凝聚力高的句子，作為分段的參考。而句子的相似度是將單字回歸到字根，再將每個字視為向量，計算兩句間的夾角值而得。所以簡言之，仍建立在一個很基本的假設 ─ 討論相同主題的文句，會使用相近的詞彙。只是文中作者也說，會因為在文章中的位置，有不同的寫作風格，例如總結的段落講的內容欠缺凝聚力，而影響的計算結果的準確。因此作者採用相對相似度的「排名」，取代絕對相似度的「分數」。

我之前提過，一個好的作者會盡量避免使用的文辭重複，但若仔細觀察人們的習慣，好的作者也會刻意塑造文辭的重複，這也許是個所謂的提示語(cue phrases)或韻律特徵(prosodic features)。我們回想一下，著名的美國民權運動領袖馬丁路德金恩(Martin Luther King, Jr.)的演說《我有一個夢》：

由於全文太長了，我就不再贅述，有興趣練習聽力的人可以到這個網站搭配文字稿，沒興趣的人也可以看中文翻譯。聰明的你應該在超聰明的我帶領之下發現，重要的句子在文章中會不斷的重複。重複的構句往往表達出文章的核心概念，而且架出了整篇文章的框架。這邊「重複」在我的歸納下可以分成幾種：

• 完全重複：例如I have a dream，通常為文件段落的切割，下一句通常是關鍵；可以將每個完全重複的下一句結合濃縮成單一主題。
• 排比重複：是最常見的重複形式，分成單句與跨句。單句內的排比往往包含表達重要概念的文句，例如廣闊的土地，勤勞的人民，悠久的歷史，這就是我們中華民族。這樣這整句是文件的關鍵；而跨句的排比，例如資訊系統與組織：blah~~~~~~~~。資訊系統與管理：blah~~~~~~~~~~~。很多作者使用這種作法架構出文件的主軸，可以作為主題的分界點。
• 對仗重複：與排比重複類似，基本上就是兩句詞性相同的句子。若這兩句連在一起，通常意義不大(可能為諺語或舉例)，但若間格出現時，如同跨句排比，會是兩個主題的分割點。
• 詞性重複：例如資訊系統可以蒐集、處理、儲存以及散佈資訊，其中對「資訊」這個概念大量的使用了動詞來修飾他，通常這種句子在文中具有相當高的關鍵性。
• 其他重複：此外還有主詞、動詞的重複，這種重複的權重較低，但是使用重複的句子通常較為重要。

以上是我粗淺的使用經驗法則的分類，沒有看過相關的研究(將重複應用在文件摘要上)；雖然有點粗糙且缺乏實證，但我想也許是一個有價值的發現吧，在這裡就坦誠的與你分享了。至於使用的方法，我最近會做一些嘗試，有進一步結果依然會在這邊跟忠實的讀者你報告。

繼續閱讀全文　中譯：進階領域獨立的線性文件分段 (Advances in domain independent linear text segmentation)

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有18 意見

找到這篇是因為看了一篇寫得非常非常好的國內論文《混合式自動文件摘要方法》(這真的寫得非常好，學習Text Mining 非常推薦以之為基礎)，想要多了解文法剖析法(Linguistic Approach)，因為文中指出Brunn所作的《Text Summarization Using Lexical Chains》提出的系統架構與我的想法相近。但後來發現命題相近的《Using lexical chains for text summarization》可能才是所謂的key paper(引用598次)，不過都翻譯了，就丟上來啦。我依照原文的章節形式分段，並用標楷體標註非作者提及的內容，文末心得處亦為我讀後的見解，為了避免讀者混淆，特別在此註明。

原文：M. Brunn, Y. Chali and C. J. Pinchak, “Text Summarization Using Lexical Chains”, Proceedings of the Document Understanding Conference, pp.135-140, 2001

摘要
文件摘要(Text summarization)解決兩個問題：選擇文件中最重要的部份以及產生清楚易懂的摘要。在本文中我們呈現2001年萊斯布里奇大學(University of Lethbridge)文件理解研討會(DUC)的一個能高效率使用詞彙鏈的摘要器(summarizer)。

一、介紹
文件摘要器選擇文件中最重要的部分與產生易懂的摘要，在本文中我們描述2001年於萊斯布里奇大學的文件理解研討會發表，基於辨認局部文件重點中最重要部分方法的摘要器。在選擇文件部分時，這個辨認也會顧及連結(connectiveness)的程度，以降低摘要中包含連結不足的句子(poorly linked sentences)。這個目標可以藉由有效的使用詞彙鏈達成。

完整的系統架構可以參考(圖1)，它包含幾個模組所組織而成的管線(pipeline)。本文的組織如下：下一段專注於介紹每個系統模組。最後我們以快速地在DUC評估分析系統的效能、概略的描述未來展望做結。

▲圖一：系統概觀

二、預處理(Preprocessing)
(一) 文件切割(Segmentation)
為了進行摘要處理，必須將原始的文件送往文件切割器(Text Segmenter)。文件切割器的角色是分割輸入的文件，使每個分割有相同的主題(Topic)。為了完成文件切割的需求，我們選擇2000年Choi 所提出的文件切割器。這個文件切割器在一個文件中產生多個區段，某些區段在內容上比其他的區段緊密。在本系統中文件切割可以獲得多重的子來源(sub-source)文件，每個文件包含討論相同主題的句子。文件切割允許接下來的模組產生更好的分析與摘要。

(二) 貼標籤(Tagging)
在分析器(Parser)中，標籤是不可或缺的，因為它包含了根據區段中語句(part of speech)所代表的意義而產生的文字分類(Classifying Words)。這個過程中文字(words)被單獨考慮，沒有考慮或指派任何標籤給語意結構(semantic structure)。在本系統中使用的標籤是1996年Ratnaparkhi 所提出的，我們選擇的原因是這個方法能夠相當精確地指派標籤。標籤器(Tagger)經由Penn TreebankWall Street Journal 語料庫的0到18段(sections) 進行預先的訓練(pre-trained)，沒有證據指出標籤器需要用明顯不同的語料庫重新訓練。

本系統也包含Ratnaparkhi’s MXPOST 標籤器套件中的工具，用以偵測句子的界線。它發表在Reynar 與 Ratnaparkhi 於1997年的文章中，是一個切斷文件使得每個句子成為獨立的一行的工具。標籤器也仰賴在Penn Treebank 大會中被標記化句子，透過由賓州大學(University of Pennsylvania)開發的sed script 工具可以轉換純文字文件成為適當標記化的版本，使文章片段成為標籤器可以接受的格式。

(三) 剖析(Parsing)
剖析是本系統最重要且耗時的模組，剖析模組集合與組織標籤後的文字，建立句法結構(syntactic structure)。我們在本系統中使用Collins 於1997年提出的剖析器(parser)。一個剖析後的文件可以在句子中依照句法的部分(syntactic position)選擇不同的元件(components)或詞組(phrases) 。舉個例子，我們可以在給定的文件中選擇所有的名詞片語(noun phrases)。尋找名詞片語對剖析過的文件可能是個瑣碎的工作，但事實上，本系統的下個階段仰賴在句子中選擇部分句法的能力。

有必要在這裡標明本文的剖析器與標籤器在輸入/輸出上並非完全的相容。剖析器接收的標籤文句必須要在開頭記錄標籤的數量，例如這句有三個標籤，就必須要在句首寫"3"，因此必須另外撰寫一個小工具計算每行中的標籤數量作為剖析器的輸入。此外，剖析器也需要接收以"word TAG"格式的文字標籤，故須將標籤器輸出中的底線(underscore)移除。

三、名詞過濾(Noun Filtering)
名詞過濾元件是一個優化器，不是文件摘要系統中必要的元件。名詞過濾從剖析過的文件中選擇性的移除名詞，提升文件摘要的精確度。以下章節描述的詞彙鏈結器(lexical chainer)輸入的是一組名詞；名詞是由標籤器從原始文件中識別產生的，但是這些名詞可能同時增強且減弱文件的主題。

比如模擬資料的傳輸包含訊號(signal)與雜訊(noise)，在訊號強且雜訊低的時候傳輸狀況是理想的；但當訊號被雜訊壓過時，傳輸變得難以辨認。與文件中的名詞一樣，形成主題的名詞像訊號，而其他就像雜訊。名詞過濾器的工作是減少「雜訊」，並盡可能地保留「訊號」。

有很多不同過濾「雜訊」名詞的探索方法，我們的概念是主要子句中名詞對主題的偵測比從屬子句中的名詞更有效。但主要子句與從屬子句的探索實為不易，所以在我們系統中，採用的是相對簡單的探索法。由於剖析器建立句子的句法結構，我們可以從原始文件中選擇不同型態的片語。我們辨識第一個名詞片語(noun phrase)以及每句中第一個次句(sub-sentence)，即主要子句、從屬子句中的其他片語裡，與第一個動詞片語有關名詞片語。使用探測產生的摘要可以在DUC評量章節中找到。此外，可以開發更複雜的的探測法以尋找辨識一句中主要子句或從屬子句的其他片語，並有其確定實驗成效的必要。

四、詞彙鏈(Lexical Chainer)
銜接(cohesion)的觀念在1976年被Halliday 與Hason 提出，是一個將不同文件部分「黏在一起(sticking together)」使文件完整的方法。一般透過文法性銜接(grammatical cohesion)如參照(reference)、代換(substitution)、省略(ellipsis)、連接詞(conjunction)；與詞彙性銜接(lexical cohesion)如語義相關詞(semantically related words)來達成。詞彙性銜接在兩個詞間與一系列相關的字之間都存在，稱之為詞彙鏈(Morris and Hirst, 1991)。詞彙鏈的演算法步驟介紹如下：

1. 選擇一組候選字(candidate words)。候選字是從名詞過濾器而來(參見第三節)，具有名詞片語或符合規則的名字功能的無限語類(open class)的字。無限語類指的是文法書中列舉不完的語類，舉例來說，代名詞、語尾助詞可以在文法書中用表格輕易的完全呈現，但是名詞、動詞卻不行，只有辭典才能囊括語言中所有的名詞、動詞，所以名詞、動詞屬於無法列完的無限語類。
2. 一組候選字可以透過分類辭典展開成相關字(senses)。本實驗中，我們使用WordNet 分類辭典(Miller et al., 1990)。本階段需要考慮所有的相關字，每個字的相關字由區別的集合表示，並建構其階層。第一層的集合是同義字(synonyms)與反義字(antonyms)，第二層是上位詞(hypernyms)與下位詞(hyponyms)與他們的變化型，如meronyms與holonyms…等等。「大冠鳩」的上位詞是「鳥」；「植物」的下位詞有「薰衣草」、「榕樹」…等。
3. 我們找到根據相關詞集合產生的語意關聯(semantic relatedness)。語意關聯存在兩個相關詞之間，當比較兩個區別字的相關詞時，會發現存在匹配(matching)的現象，兩組字中有交點存在。每個語義關係決定在匹配的路徑長度，該長度與兩個比較集合的階層有關。這句意思應該是語意關係決定在兩個文字概念的距離，距離可以透過將文字概念展開而成的相關字sense之間的距離得出。因為sense是有層次的，所以如果A延伸出來的第2層sense與B延伸出來的第3層sense交疊，則A與B兩個概念的距離就是5，應該啦。
4. 我們建立詞彙鏈如下：
   
   當_i≠_j時，word_i-sense_ix與word_j-sense_jy有語義相關
5. 我們透過以下的偏好準則(preference criterion)，保有最長的詞彙鏈：
    
   在我們的實作中，偏好藉由對詞彙鏈中對每個成對的語義關聯指派分數來處理，然後進行分數的加總。因此語彙鏈的分數是基於語彙鏈的長度與成員間關係的型態。成員間關係的型態應該指的是同義詞、反義詞、變化型…等。

在語彙鏈方法中，兩個字在語彙鏈中的關係是兩兩相互的，即是每個相關字(word-sense)都必須其他每個語彙鏈中相關字有語義上的關係。在文件中無限語類字的順序與建立語彙鏈無關。但儘管如此，無限語類的字產生極大量的語彙鏈，因此產生文件更大區段的問題。面對此問題，當遇到長文件的切割時，我們只保留相關字的描述中的同義字；這樣的刪減還能使得效果比基於ISA-2/INCLUDE-2 來的好。此外，也可以從太多單獨區段的狀態下窄化詞彙鏈集的詞幹(stemming)。至於什麼是"ISA-2/INCLUDE-2"我也不知道…如果讀者知道的話請告訴我吧:)

語彙鏈法藉由一組呈現消歧義(disambiguation)相關字的候選集合，整合相關字消歧義的過程。消歧義指的是消除由於不同一詞多義所引起的混淆，例如「大學」既是教育機構又是一本古書，故必須要進行消歧義了。在演算法步驟5的偏好準則中，只保留成員是相關詞的語彙鏈，這些相關詞成為銜接文件的指標。

語彙鏈計算了每個文件區段，作為下一階段的文句萃取器的輸入。

五、文句萃取器(Sentence Extractor)
文句萃取器模組有兩個步驟：區段選擇與文句萃取。

(一)區段選擇(Segment election)
本階段的目標是從文件中選擇與主題相關的文章區段。文章區段選擇的演算法基於區段的評分，如下所示：
 
score(chainMember_i, seg_j)是chainMember_i在seg_j出現的數量，m是他們的數字，s_i是chainMember_i中區段的數量。

系統選出分數前n高的區段進行文句的萃取。

(二)文句萃取(Sentence extraction)
每句被以詞彙性銜接的總分排名，排名程序的目標是評定每個分數的重要性、為每句結合所有分數成為排名。為了達成這樣的作業，我們根據Hoey 在1991年的實作，為詞彙性銜接定義句子必要連結的最小的數字作為門檻。我們加總超過門檻的句子之詞彙性銜接分數作為句子的排名。根據我們的實證調查，在我們實驗中門檻值為2最為恰當。

每句以與其他句子共享語彙鏈的數量總和為排名。更精確地說，sentence_i的分數是決定在sentence_i與區段選擇階段時sentence_i所包含的語彙鏈的字的數量。

這樣的摘要包含句子的排名清單，因此可以依照需求的壓縮比例調整原始文章的呈現。

六、DUC評量
我們參與單篇文件的DUC評量，評量的工作包含從給定的文件中建立一個近100字長度的摘要。系統輸入30組，每組約10份的文件。根據我們的分析，結果前景看似光明。在語法性的部分，我們產生的摘要獲得3.73分(滿分4分)；同樣的，銜接(cohesion)與組織(organization)分別得到2.55、2.66分(滿分4 分)。我們摘要器評量的重要資訊彙整如下(表1)：

▲表一：評量結果

我們找到排名高分的句子幾乎每次都是都是最重要的。此外，由於句子的萃取包含參考措辭(referring expressions)，對我們的系統來說仍是個問題。

七、結論與未來展望
在本文中，我們實作一個高效率詞彙性銜接法的摘要引擎系統。排名的程序使用文件「相關(aboutness)」的方法，在符合使用者需求的摘要比率的文章中選擇最重要、最佳連結的句子。未來，我們計畫進行以下問題的研究：

• 我們的方法將完整的句子視為單元萃取，使用壓縮技巧(compression techniques)可以提高摘要的縮減並增加品質(Barzilay, McKweon, and Elhadad, 1999; Mani, Gates, and Bloedorn, 1999; Jing and McKeown, 2000; Knight and Marcu, 2000)。
• 我們摘要的方法只使用語彙鏈代表原始文件，在產生摘要時也可以考慮採用其他聚合(gathered)文字的方法。
• 在名詞過濾的程序中，我們的假說是去除從屬子句的名詞。我們也許可以進一步證明，根據子句出現處的種類計算權重值的有效性。

心得
我想讀到這你也累了，所以應該沒什麼腦力再看我的心得吧，然後說真的我也累了…我一直覺得這篇只是把很多方法兜起來，看不到真正想看的東西…例如語彙鏈的內容，不過本文提出了很好的模組架構。因為是兜起來的，內容有點過於精簡，也不適合入門讀者，而我最關心的主題切割也沒有加以說明，只指出了一篇論文標題，所以整體而言是失望的。

理性面而言，作者使用名詞過濾將他認為重要句子中的名詞片語挑出，建立語彙鏈，再透過語彙鏈定義分數，萃取出分數大於門檻的句子，所以我認為語彙鏈在本研究充其量只是一個「計算分數的方法」，但卻使用了大量的文法剖析、拆解句子、抽取名詞、語彙關聯…我不知道是否有其必要。此外，我認為語彙鏈的分隔度不會太大，且語彙鏈的設計與結果好壞息息相關，語彙鏈不只複雜，而且資訊含量驚人，設計成本相當可觀。至於為什麼說分隔度不會太大，是因為我想語彙鏈(Lexical Chain)其實就是本體論(Ontology)吧！由於有大量的連結，也是一種網路的構造，故可以套用六度分隔理論，在六度分隔理論的假設下，根據我先前做的實驗(關鍵字六度分隔)，最長的連結也頂多需要走九步，但這九步可能需要尋覽完所有的詞彙。

閱讀本文的時候，我參考了《中國話的文法》與《上位詞語下位詞的篇章功能》，這兩篇都不是以電腦科學的角度出發，純粹探討語言學的，我覺得他們都寫得很好，也在其中獲得了許多重要的知識。我想中文摘要就詞性而言，比英文難上許多，在《利用向量支撐機辨識中文基底名詞組的初步研究》(這篇論文的"卡司"非常強大，作者來自台大資工/外文與政大資科)提到，中文的動詞可以修飾名詞，會造成複合名詞的誤判，例如「建設公司」與「流浪教師」等。所以是否有更直覺抓重點的方法，就像人不需要知道名詞動詞，只需要靠一種fu，一看就知道哪句是重點，抓起螢光筆馬上作個記號這麼容易呢？

繼續閱讀全文　中譯：使用語彙鏈建立文件摘要(Text Summarzation Using Lexical Chains)

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有6 意見

「資訊種子」不限資訊相關科系學生參加，是台北縣電腦公會辦的公益(免費)活動，為期一年。聘請經理級以上講師固定於周六下午上課(課程內容包含資訊產業、數位內容、生涯規劃、智慧財產…)，此外還有企業參訪、專案參與及海外參訪，最重要的是，誠如我說的，可以完成學生階段「認識不同領域的優秀人才」的目標。

 
▲想要成為眾所矚目的焦點，加入資種，你也可以！

好了，其實已經差不多介紹完了！我認為在資訊種子最大的收穫是能夠認識許多優秀、負責且活躍的同儕，這些人脈的培養將會使你在未來的人生上左右逢源。舉個簡單的例子，據我所知，本屆資訊種子的學員報名微軟實習計畫全部都錄取了，由此可知將資訊種子比喻為成功的搖籃毫不為過。

參加資訊種子的人都很厲害耶…我行嗎？
朋友看到了七屆錄取名單，對我說：「資訊種子的學員都很厲害，我怕我不行耶…」。我對他說：「如果你參加了，你就有機會認識34個厲害的人；如果你放棄了，你只能活在原來的小圈子，不知道厲害的人怎麼看事情…」

出自私校的我很清楚總會有點自卑，但是資種也不是只有名校的學生阿。我們要相信：近朱者赤、近墨者黑，應該要更正向的思考，這是一個很難得的機會，因為將來出社會後，生活的範圍常常是同質性的人；在一般的學校團體，也很難認識來自其他學校優秀的人脈…你該不會想著藉由國中同學、高中同學認識不同學校的人吧…那樣是很有限的，而且沒有共事過也不會患難見真情！

▲策畫台北縣電腦公會的春酒大會，為資訊種子的「春酒專案」。當天與會來賓包括行政院、資策會長官，台灣各縣市電腦公會理事長與產官學界大老。

資訊種子在幹什麼呢？
不知道為什麼總是有朋友對我說不知道資訊種子網站在寫什麼，我這邊具體的再介紹一下好了：

▲大宇資訊總經理為我們介紹《數位遊戲產業的趨勢與經驗》

• 不清楚上課內容？我的上課筆記(雖然沒有每堂課都記到)詳實的紀載老師的一言一行，堪稱資訊種子筆記經典之作 ；孟芳的課程回顧透過生動的描述與豐富的照片，提供你不一樣的視野
• 不清楚學員上課後的看法？這裡彙整了大家每堂課的心得，也許可以在心得中找到線索
• 看看七屆學員怎麼說？元智資傳 劉孟芳、台大農經 柯捷方、台大電機 薛仲祥、中正企管 陳識傑、政大公行 張桂慈、元智工管 程紹幃、成大醫工 陳玟伶…(陸續追加中!!!)

如何參加資訊種子？
當然你要先報名。接著為了考驗你的態度，你必須繳交一些資料，經過審核後會安排面試。身為熱愛分享的我也不改風格在這裡跟你分享我當年的資料供你參考，不過你要記住，照抄絕對不是一個好的態度:D

• 未來一年的規劃
• 第一題(注：鑒於與今年題目相關，為了避免爭議與提高公平性，暫時將連結拿掉，將於報名截止後恢復)
• 數位落差的原因與改善方式

最後，如果你順利進入第一階段，你可以參考我的面試心得進行準備。在此附上同學的面試心得：台大生工 王皓、元智資傳 劉孟芳(含資種人物介紹)。總之，若想改變人生，資訊種子一年的培訓將會是個不錯的選擇！還等什麼？8/26報名就截止了，機會是不等人的哦：

[資訊種子培訓計畫官方網站]

btw，說真的，我的Blog讀者以在職者居多，寫這些似「太青春」而幫不了什麼人XD

繼續閱讀全文　資訊種子：即將大三到碩一的你 請讀這篇可能改變你一生的文章

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有5 意見

「人生的課題，如果你沒有學會處理，它就會一而再、再而三的讓你練習」…其實也沒那麼嚴肅啦，只是小時候沒學好，最近讀論文的時候一直碰到馬可夫鏈…讓我覺得很卡，於是想說花一些時間把這個關節打通。我希望用一些淺顯易懂的文字寫一些老嫗能解的馬可夫鏈概念(千萬不要像維基百科寫得像天書般)，這就是邊學邊寫的最高境界吧，我想！

▲當我聽到「馬可夫鏈」的時候，總會想像一條長長的鏈子，鏈住馬的頭@@

正文開始
我們想像有一些加以編號的桶子，每個桶子裡面裝著數顆編號過的球，如下圖所示：

▲有1~n個桶子，桶子中的球也編有1~n號

接下來玩法是這樣的，例如我們先在2號桶子中抽到3號球，於是我們就跑到3號桶子再抽一顆球；我們發現3號桶子抽出來的球是5號，於是又跑去5號桶子抽…總之從任一個桶子中抽出球的號碼，決定著接下來目的桶子的號碼，然後一直抽到沒完沒了(或某個次數)，如此所形成的連續動作就是馬可夫鏈！

到這裡已經講完馬可夫鏈了，應該有如醍醐灌頂的感覺吧！那我們接下來看看，這樣的一條鍊子有什麼特別的呢？

馬可夫鏈的特色
馬可夫鏈最主要的的特色在於「下一個狀態決定於上一個狀態裡的機率」，以上面桶子抽球的例子來說，第k次抽球的桶子決定在第k-1次所抽出來的球(與前面抽球的機率都沒有關係)。此外，在同一個時間，馬可夫鏈只會有一個狀態，我們舉下一個例子：慈善賭場中有一個賭徒，身上只有一塊錢，每賭贏一次多一塊，輸一次少一塊(因為是慈善賭場，輸到負的還可以繼續賭XD)。

這樣也構成一個馬可夫鏈，第k次賭博身上所剩的錢，決定在第k-1次身上的錢&輸或贏，所以我們若知道第k-1次身上有10塊錢，就可以推論第k次輸了的話身上剩9塊錢，贏的話會有11塊錢。此外，我們還可以發現，狀態是可能來回循環的，例如可能會重複回到「一塊錢」的狀態。但是如果是三度空間以上的馬可夫鏈，狀態會離原點越來越遠(雖然不一定沿著固定方向)。

總而言之，馬可夫鏈有以下兩點特色：

• 在任何週期，系統中的事件只存在於一種狀態內。(每一局身上的錢只有一種狀態)
• 事件由一種狀態轉換到另一種狀態時的機率，決定於前一週期。(第k局加減的錢由第k-1局的機率所決定)

計算馬可夫鏈
一般而言，我們會使用轉移圖來了解馬可夫鏈狀態間的轉換，再搭配矩陣來計算馬可夫鏈的數值。一開始我們可以使用樹狀圖來分析馬可夫鏈，如下圖：

▲以上三張圖都在表示同樣結構的馬可夫鏈，a1, a2, a3 為三種狀態，而互相轉換的機率標在線上

我們都會使用矩陣來進行馬可夫鏈的計算，透過反覆的計算，例如計算第k步時停留在a1狀態的機率，達到一個程度的預測。

總結
馬可夫鏈的應用相當多，可以用來進行物理中排隊理論或統計學的建模，此外也可以應用在人口、生物觀察上(估計的繁殖或死亡狀態)。最值得一提的是，基於馬可夫鏈發展出狀態非顯而易見的隱藏式馬可夫模型(HMM)大量的被應用在辨識技術上，如語音辨識與文件切割等，這也是為什麼馬可夫鏈重要的原因。

參考資料：

• 馬可夫鏈的簡介：這是一篇從概念講起馬可夫鏈的文章，雖然後面寫得有點讓人想飄走，但是可以對馬可夫鏈有個概觀的了解。
• Ch 10 馬可夫鏈.ppt：朝陽科大資管系李朱惠老師的上課教材，使用例題介紹馬可夫鏈的運算

繼續閱讀全文　什麼是 馬...馬可夫鏈(Markov Chains)？

• 編輯文章
• 此文章網址
• 轉寄此文章
• 目前有9 意見