• 學位論文

基因演算法結合二階段最佳化演算法解決集合涵蓋問題之研究

最佳化問題中有一廣為周知的問題為集合涵蓋問題(SCP)，因其可作為許多資源選擇問題的模型，因此在現實生活中有許多重要的應用。由於集合涵蓋問題為一NP-hard問題，而基因演算法也常被使用來求解此類問題，且可獲得不錯的結果。本論文設計一混合式基因演算法(TGA)，其結合二階段最佳化演算法（TPOA）與基因演算法（GA）來求解集合涵蓋問題。TGA使用TPOA來產生GA之初始族群，能夠盡可能產生一些好的基因於族群中，並保證其在族群中有一定的數量，以提高這些好的基因在早期於族群中之存活率，期望這些好的基因能夠提供GA快速的收斂，以及提高尋找最佳解的機會。由實驗結果顯示，TGA可較使用亂數產生族群之Beasly和Chu所提出的GA (BeCh GA)能在短時間內得到較佳的解，而在長時間中兩者則是差不多的。因此TGA提供一增加GA初始族群之多變性與強化性之系統化架構，可以有效的讓GA在短時間內獲得一近似最佳解，而不減少GA尋找最佳解的機會。

• 學位論文

以字句擷取為基礎並應用於文件分類之自動摘要之研究

摘錄式（Extractive）摘要旨在於從原始文件中依據摘要比例自動選取一些重要的字句、段落或章節，並按順序將其形成簡潔摘要。大多數常見的摘要模型原則上可依據其特性分為兩種比對策略。其一，以逐字比對（Literal Term Matching）的方式評估字句與文件的相關性，這其中以向量空間模型（Vector Space Model, VSM）為代表；其二，以概念比對（Concept Matching）的方式評估，這其中以潛藏語意分析（Latent Semantic Analysis, LSA）為代表。 基於這些觀察，在本研究中我們提出數種自動文件摘要的改進方法。在逐字比對上，研究隱藏式馬可夫模型（Hidden Markov Model, HMM），並對其兩種變化（型一及型二）做廣泛的探討。於隱藏式馬可夫模型-型一：視文件為一生成模型（Generative Model），對於每個索引都有一對應的機率分佈，文件與文件中每一字句的相關性，是藉由字句的所有索引，被文件模型生成相似值（Likelihood）的連乘積來決定，換句話說當字句含有較高的相似值，則其與文件的相關性就越高；於隱藏式馬可夫模型-型二：則視文件中每一字句為一機率生成模型，文件中每一字句與文件的相關性，是藉由文件被字句生成的相似值來決定，並且文件中各字句可依據其所產生的相似值作排序。另一方面，在概念比對上，提出兩種摘要模型，分別為嵌入式潛藏語意分析（embedded LSA）與主題混合模型（Topical Mixture Model, TMM）。於嵌入式潛藏語意分析：文件與文件中每一字句同時參與潛藏語意空間的建構，並且字句的重要性可經由適當評估在潛藏語意空間內，其向量表示式與文件的相關性而得；於主題混合模型：文件中每一字句被分別表示成一混合模型，並由K個潛藏主題分佈及其相對應特定文件的事後機率所組成，文件中每一字句與文件相關性，即可藉由文件中索引發生在潛藏主題及字句產生各別主題的機率值來評估。我們在中文語音廣播新聞語料庫上執行了一系列的實驗，實驗結果顯示使用隱藏式馬可夫模型或主題混合模型其結果較其它常見方法有顯著的提升，同時主題混合模型在幾乎所有情況下均較隱藏式馬可夫模型來得佳。 最後，我們也研究摘要模型中主題混合模型在文件分類的適用性，並且文件也能預先經由上述摘要模型做前處理。初步實驗結果顯示，主題混合模型分類器較常見K-最近鄰（K-Nearest-Neighbor, KNN）分類器在分類的效果上有些微的提升。 關鍵字：摘要、潛藏語意分析、隱藏式馬可夫模型、主題混合模型、 K-最近鄰分類器

• 學位論文

容許多次錯誤回應之演繹競局問題之研究

• 學位論文

偽幣問題之改良演算法設計與分析

偽幣問題由來已久，有許多人不斷的增加不同的條件，使得這個問題變得更具挑戰性也更加困難，也有許多人嘗試著提出各種不同的演算法去解決這些不同形式的偽幣問題。在本論文中，我們對兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題提出了改良的演算法，以及改進了李立中的三枚以上偽幣知其輕重演算法，使之成為三枚以上偽幣不知其輕重的演算法。在最後我們也對一枚偽幣知其輕重、一枚偽幣不知其輕重、兩枚偽幣不知其輕重、三枚偽幣知其輕重、三枚偽幣不知其輕重、四枚偽幣知其輕重、四枚偽幣不知其輕重等問題，提出了分析，說明各個演算法相對於理論下限還有多少可以努力的空間。

• 學位論文

最小化音素錯誤鑑別式聲學模型學習於中文大詞彙連續語音辨識之初步研究

近來，有不少文獻針對鑑別式聲學模型訓練加以研究改進，本論文則延伸最小化音素錯誤(Minimum Phone Error, MPE)聲學模型訓練及調適，並使之應用在中文大詞彙連續語音辨識上。本論文以公視新聞外場記者語料作為實驗平台，在實驗中，先對聲學模型進行最大化相似度(Maximum Likelihood, ML)聲學模型訓練，再來則比較最小化音素錯誤與最大化交互資訊(Maximum Mutual Information, MMI)兩種鑑別式訓練，最小化音素錯誤訓練相較於最大化相似度訓練能大幅降低15.52%的相對音節錯誤率、12.33%的相對字錯誤率及10.02%的相對詞錯誤率，明顯優於最大化交互資訊的訓練方式。此外，在非監督式聲學模型調適上，本論文探討了在聲學模型空間及特徵空間上透過轉換矩陣間接調適的調適技術。然而，因為缺少正確轉譯文句(Correct Transcripts)可供最小化音素錯誤估測原始正確率，故需以辨識所產生對應的轉譯文句來取代，使得非監督式最小化音素錯誤調適技術無法對聲學模型參數做良好的估測，導致辨識效能顯著地下降。為了改善此現象，本論文提出了「原始正確率預測模型」(Raw Accuracy Prediction Model, RAPM)用來改良非監督式最小化音素錯誤之調適，對辨識效能有少許的提升。