模糊歸納學習演算法在平行迴圈排程之應用

Abstract

在實際的應用中，提供給學習系統的資料通常包含模糊資訊，而傳統的符 號學習演算法無法推論這類的資料。例如，在平行編譯的應用領域中，平 行迴圈排程是非常重要的，因為每一個迴圈都包含一些可以表示其特性的 屬性，在過去，我們已經實際製作出一個基於知識庫方法的平行迴圈排程 方法，簡稱為KPLS，其可以針對不同的迴圈去選擇合適的平行迴圈排程， 將迴圈分配至多處理器系統中以達到高執行效率，我們利用這些迴圈的屬 性讓KPLS中的推論機推論出合適的排程演算法，但是，這些屬性包含了模 糊的資訊，並不適合用傳統的符號學習演算法來推論其概念規則。在本篇 論文中，我們將模糊集合理論應用於AQR學習演算法，簡稱FAQR，此演算 法可以從訓練例子中歸納出模糊語言規則，因此被用於解決上述平行迴圈 排程的問題，並且找到準確的推論規則，這些規則可以推論平行迴圈排程 ，此外FAQR亦被用於解決鳶尾花的分類問題，在這兩個實驗中，其實驗結 果都非常良好。 In real applications, data provided to a learning system usually contain fuzzyinformation. The conventional symbolic learning algorithm can not infer data that contains such kind of information. For example, in the application domainsof parallelizing compilers, parallel loop scheduling is very important becauseeach loop contains some attributes that can indicate its characteristics and property. In the past few years, we have designed and implemented a parallel loop scheduling based upon knowledge based approach that is called KPLS to choose an appropriate schedule for different loop to assign loop iterations toa multiprocessor system for achieving high speedup rates. Based on these attributes mentioned above, an inference engine of KPLS is used to choose suitable scheduling algorithm. Unfortunately, we found that these attributes contain some fuzzy information, which are inapplicable to the traditional symbolic learning strategy for inferring some concept descriptions.In this thesis, we apply fuzzy set concept to AQR learning algorithm that is called FAQR. FAQR can induce fuzzy linguistic rules from fuzzy instances, is then proposed to solve the above parallel loop scheduling problem. Some promising inference rules have been found and applied to infer the choice of parallel loop scheduling.Besides, we apply the fuzzy inductive learning algorithm in IRIS Flower Classification Problem. Experimental results show that our method yields high accuracy in both different domains.