第四章 人工智慧演算法 2018/9/19.

Presentation on theme: "第四章 人工智慧演算法 2018/9/19."— Presentation transcript:

1 第四章 人工智慧演算法 2018/9/19

2 Case-based Reasoning (案例式推論)
案例式推論解決問題的流程: 確認問題的狀態 由過去案例中找尋相似的案例 由相似的案例獲取經驗以解決目前的問題 將目前的問題及解決的方法加入案例中 2018/9/19

3 案例式推論解題的關鍵因素 案例特徵(參數)之訂定 案例特徵(參數)權重之訂定 案例特徵(參數)比對演算法之訂定 2018/9/19

4 案例式推論運作流程 案例建制 案例擷取 案例調整 使用者 新案例 重複案例 案例知識庫 結果 需求 調整參數 查詢模式 適合的 案例 查詢
2018/9/19

5 案例式推論實例: 自動化郵件回覆客戶服務系統
以郵件進行客戶服務己成趨勢 現有的郵件客服有下列缺點 郵件回覆為人工進行 需要浪費人力回答重覆問題 無法保證即時回覆 目標: 將傳統郵件回覆自動化 縮短客戶等待時間 提高客戶的滿意度 節省客服中心的人力應用 2018/9/19

6 自動化郵件客服系統功能 自動辨識郵件目的及問題 搜尋最適合客戶的解決方案 即時產生回覆郵件 調查客戶滿意度 從雙方面調整資料庫
2018/9/19

7 自動化郵件客服系統架構 Q&A儲存機制 詞庫 網 際 問題分析機制 路 Q&A 資料庫 客服人員介面 Mail Server 解答機制
使用者 Mail Server 解答機制 客戶 資料庫 自我學習 機制 客服人員 2018/9/19

8 客服系統權重演算法 權重調整： 一名詞在所有集合中出現的頻率愈多，代表此詞為一冗詞
一名詞在所屬集合中出現的頻率愈多，其他集合中出現的頻率愈少，即有可能就是關鍵詞 2018/9/19

9 客服系統權重演算法(cont.) Wij=(pij – nij)/N wij 關鍵字i對在文章j的權重 N 取樣總篇數
pij 關鍵字i在文章j出現的次數 nij 關鍵字i在文章j之外出現的次數 2018/9/19

10 客服系統關鍵詞比對演算法 FAQ關鍵詞比對： 比對客戶詢問問題與資料庫中的資料相似程度
給予一個問題與資料庫中各筆資料介於0至1的分數，並找出分數最高的資料 2018/9/19

11 Neural Networks (類神經網路)
1943　McCulloch 與 Pitts首度提出正式的類神經計算單元。 　 1949　Donald Hebb提出第一個學習法則---Hebbian learning rule。 1954　Minsky 首度建造類神經電腦並測試。　 1958　Frank Rosenblatt 發明感知機 (Perceptron)﹐可調整連接值。 1960　Bernard Widrow 與 Marcian Hoff 提出 Widrow-Hoff 學習法則　 1965　Nils Nilsson 綜合當代研究並提出學習機所受的限制。 　 1972　Sun-Ichi Amari 提出有關臨界值的數學理論。 1982　Kohonen 研究非監督模式網路﹐建立陣列式神經元。 　 1982　Stephen Grossberg 與 Gail Carpenter研究調適性迴響網路。 　 1986　James McClelland 與 David Rumelhart加入平行分散式計算技巧。 2018/9/19

12 類神經網路的優缺點 Advantages Criticism prediction accuracy is generally high
robust, works when training examples contain errors output may be discrete, real-valued, or a vector of several discrete or real-valued attributes fast evaluation of the learned target function Criticism long training time difficult to understand the learned function (weights) not easy to incorporate domain knowledge 2018/9/19

13 - f A Neuron mk å weighted sum Input vector x output y Activation
function weight vector w å w0 w1 wn x0 x1 xn The n-dimensional input vector x is mapped into variable y by means of the scalar product and a nonlinear function mapping 2018/9/19

14 Training a Neural Network
To obtain a set of weights that makes almost all the tuples in the training data classified correctly Steps Initialize weights with random values Feed the input tuples into the network one by one For each unit Compute the net input to the unit as a linear combination of all the inputs to the unit Compute the output value using the activation function Compute the error Update the weights and the bias 2018/9/19

15 Back-Propagation Neural Network (倒傳遞類神經網路)
2018/9/19

16 範例－圖形辨識 Ａ Ａ ００１０１１１０１ ０１００１０１０１ ＞０ ＞０ Ｂ ＜０ 2018/9/19

17 倒傳遞類神經網路演算法 Step 1: 以最小化能量函數的結果為目標，計算訓練資料輸入向量與目標輸出向量之間的平均平方差（Mean square error）。 Step 2: 以下列公式調整修正權重值： 其中 且  為學習率（Learning rate）。 Step 3: 以類似的方式調整修正門檻值。 Step 4: 重複Step 1到Step 3，計算所有的訓練資料輸入向量。 Step 5: 利用測試資料測試以上訓練的網路，假如收斂，則停止；否則跳到Step 1。 2018/9/19

18 範例－ B型肝炎檢驗分類 (劉威良提供) 抽血檢驗 表面抗原 (HBsAg) 陽性者 為 帶原者 表面抗原 (HBsAg) 陰性者 為
非帶原者 2018/9/19

19 研究問題(B型肝炎感染後的演變 ) 成人B型肝炎 病毒感染 5%~10% 慢性帶原者 50%~60% 無病狀感染
30%~40% 有病狀急性肝炎 慢性肝炎 健康帶原者 恢復 1%~3% 猛爆性肝炎 慢性 活動性肝炎 慢性 持續性肝炎 肝硬化 肝癌 2018/9/19

20 研究問題（1/2) 轉態 的意思並非B型肝炎好了，而是指感染情況有改善（肝臟的發炎情況有改善），此時必需停藥
2018/9/19

21 研究問題（2/2) 錯 是 生命危害 抗藥性 轉態 不轉態 轉態 不轉態 預測轉態 用藥 不用藥 預測不轉態
病毒不轉態必需用藥控制，轉態則必需停止用藥以免產生抗藥性 預測轉態失誤將對人體造成嚴重後果 2018/9/19

22 特徵擷取 依照醫師診斷重要參數，再加以推廣 醫師診斷重要參數 anti-HBs (B型肝炎表面抗體) anti-HBe (B型肝炎e抗體)
anti-HBc (B型肝炎核心抗體) 　 HBsAg (B型肝炎表面抗原) HBeAg (B型肝炎e抗原) HBcAg (B型肝炎核心抗原) HBV DNA (B型肝炎病毒DNA) 2018/9/19

23 以倒傳遞網路預測B型肝炎檢驗分類的主要建置步驟
步驟一：輸入抽血樣本資料（訓練範例）　　　　　　　　　　 步驟二：將抽血資料予以正規化 步驟三：依照資料屬性相關程度分為若干類 步驟四：計算類神經網路節點數 步驟五：分別給予各類別之個別目標值 步驟六：設定輸入值與輸出值並且開始訓練 步驟七：進行測試，觀察是否符合理想的預測率 2018/9/19

24 正規化 (Berry and Linoff, 1997) 2018/9/19

25 正規化範例 以ALT（肝發炎指數）為例 正常值Range ：5.00 - 55.00 調整後Range ：4.95 - 55.05 正規化
2018/9/19

26 取二個參數為範例（設定初始值） X1=1 X2=1 w13=0.5 w14=0.9 w23=0.4 w24=1.0 w35=-1.2
θ3=0.8 θ4=-0.1 θ5=0.3, 1 2 2018/9/19

27 計算隱藏層 3 4 2018/9/19

28 計算輸出層 5 2018/9/19

29 計算輸出層輸出值誤差和誤差梯度 及調整隱藏層－輸出層權重值
2018/9/19

30 計算輸出層輸出值誤差和誤差梯度 及調整隱藏層－輸出層權重值(公式)
2018/9/19

31 計算隱藏層輸出值誤差和誤差梯度 及調整隱藏層－輸出層權重值
2018/9/19

32 計算隱藏層輸出值誤差和誤差梯度 及調整隱藏層－輸出層權重值(公式)
計算隱藏層輸出值誤差和誤差梯度 及調整隱藏層－輸出層權重值(公式)　 2018/9/19

33 更新所有權重及門檻值並進行 下一個樣本(公式)
更新所有權重及門檻值並進行 下一個樣本(公式)　 2018/9/19

34 完成權重調整 進行下一個樣本參數 2018/9/19

35 停止條件 每一組樣本數皆計算錯誤(Error)值，當所有樣本測試完，則計算平方誤差總和SSE(Sum of Squared Errors) ，直到SSE < 0.001為止 2018/9/19

36 Genetic Algorithm(基因演算法)
源自於John Holland在1975 年出版的著作Adaptation in Nature and Artificial Systems 仿效自然界生物進化過程 透過基因的選擇(selection)交換(crossover)及突變(mutation)產生更好的下一代 選擇(selection)過程 較高合適值(fitness value)就有較大機會獲得保留 較低合適值的解答，可能會遭到淘汰 較不易陷入local optimal 2018/9/19

37 Genetic Algorithm(基因演算法)
Population (族體): Encoding (編碼): Crossover (交配): Mutation (突變): Selection (適者生存): Fitness Function (適合度公式): 2018/9/19

38 基因演算法交配運算 基因演算法突變運算 基因演算法流程圖
Crossover randomly selects one-cut-point and exchanges the right parts of two parents to generate offspring. 基因演算法交配運算 Mutation alters one or more genes with a probability equal to the mutation rate. 基因演算法突變運算 基因演算法流程圖 2018/9/19

39 多目標最佳化配題機制 從大量試題中，選取符合出題方向和條件的試題，進行配置，組成最佳鑑別度試卷
指定測驗時間範圍的試題配置問題模型 (Dedicated Range of Assessment Time Problem-DRAT) 符合期望測驗時間最高界限和最低界限的多目標配題機制。 固定題數的試題配置問題模型 (Fixed Number of Test Items Problem – FNTI) 符合固定試卷試題數量的多目標配題機制。 2018/9/19

40 指定測驗時間範圍的試題配置問題 (DRAT)
x1 x2 x3 x x98 x99 x100 … DRAT目標函式： 　　Maximize Z = DRAT限制式： Xi = 0 or 1, i = 1, 2, …, n　　 1 1 1 在測驗的實施過程中，教學者經常會以指定測驗時間範圍為主要條件，並配合其他參數的限制，我們將此問題稱為「指定測驗時間範圍的試題配置問題」(Dedicated Range of Assessment Time Problem)，簡稱DRAT問題 決策變數(Decision variables) xi：當第i個試題被選取時，xi 為1 ；否則，為0; 參數 ti：試題Qi的估計回答時間； 參數 di：試題Qi的鑑別度； 參數 rij：試題Qi對概念Cj的相關程度； 參數 hj：期望試題相關概念Cj的最低界限； 參數 l：回答被選取的所有試題，所需花費的期望測驗時間的最低界限(lower bound)； 參數 u：回答被選取的所有試題，所需花費的期望測驗時間的最高界限(upper bound)； 變數xi 表示試題配置結果中，第i試題是否被選取，xi 為1時，表示第i試題被選取，為0，則反之。 限制式(1)表示，被選取的所有試題與各概念間的相關程度總和不可低於期望相關程度，以使試卷的測驗概念能符合出題方向。 限制式(2)和限制式(3)分別明確指定被選取的所有試題期望測驗時間總和的最高界限和最低界限。 在目標函式Z中yyyyyy表示所有選取出的試題鑑別度總和，而xxxxxx則表示被選取的試題數目 選出的試數量是不定的 2018/9/19

41 DRAT的試題配置基因演算法 (1/5) 概念程度下限先決基因演算法 (Concept Lower-bound First Genetic approach – CLFG) CLFG的進行步驟 1.建立母體(Encoding) X 為染色體，包含有 n 個基因 X = [x1 , x2 , …, xn] X = [0, 0, 1, …, 0] 第i個試題被選取時，xi 為1 ；否則，為0； 為了處理指定測驗時間範圍的試題配置問題 (Dedicated Range of Assessment Time - DRAT)， 我們提出一個概念程度下限先決基因演算法(Concept Lower-bound First Genetic approach - CLFG)來解決 設變數X為母體中的染色體，包含有n個基因變數，X = [x1, x2, …, xn]，當第i個試題被選取時，xi 為1 ；否則，為0;； S表示一個集合，該集合中包含母體全部的染色體； K表示母體中染色體的數量； Sk表示母體S中第k個染色體。 首先隨機產生一組用二元(binary)變數表示方式的各組試題序列的染色體，例如X = [0, 0, 1, …., 0]。 2018/9/19

42 DRAT的試題配置基因演算法 (2/5) 2.適配等級(Fitness ranking) R = dc  ipt dc =
 = w  dtl  ipt_l w = ( in di xi) / average(u, l) dtl = 適配函數　v(Sk) =  = w  dtu  ipt_u dtu = 我們利用適配函數(fitness function)來計算染色體的適配值，當適配值愈高的染色體，愈能符合我們所設定的目標函式和限制條件，在演化(Evolution)的過程中經篩選(selection)後留下的機會也愈大，進而再繼續交配、繁衍和篩選，如此重覆終而演化成最符合要求的試題配置組合。 我們為了讓染色體在基因演算法運算時，能夠快速的演化，所以在適配函數中加入使用處罰方法，加速適配值的收斂。 為了讓被選取的所有試題與各概念間的相關程度總和不可低於期望相關程度，以使試卷的測驗概念能符合出題方向， 讓低於期望相關程度的試題配置組合獲得較低的適配值。 定義一個處罰函數，以在求解過程中讓結果接近符合所設定的限制式，處罰函數定義為R = dc  ipt， R 為針對試題組合的概念總和低於期望相關程度的處罰分數，dc=表示被選取的試題與各概念間的相關程度，低於期望相關程度的概念差距總和 ipt為使用者對概念相關程度所定義的處罰權重 另兩個限制式而設定的處罰函數，分別為當試卷測驗時間不超過期望測驗時間的最低界限，或超過期望測驗時間的最高界限。 當試卷測驗時間不超過期望測驗時間的最低界限時，處罰函數為 = w  dtl  ipt_l，  為針對試卷測驗時間不超過期望測驗時間最低界限的處罰分數， w 是被選取的試題之加權平均鑑別度(被選取的試題之鑑別度總和除以期望測驗時間最高界限和最低界限的平均)，用意是可利用被選取試題的平均鑑 別度大小，來予以處罰扣分，當平均鑑別度愈大，則扣分愈多，若平均鑑別度愈小，則扣分愈少，讓基因演算法在求解過程加重限制式的重要性 dtl表示被選取的試題組合之估計回答時間總和，不超過期望測驗時間最低界限的差距值， ipt_l為使用者對試卷測驗時間不超過期望測驗時間最低界限所定義的處罰權重。 當試卷測驗時間超過期望測驗時間的最高界限時，處罰函數為 = w  dtu  ipt_u  為針對期望測驗時間最高界限的處罰分數， w 是被選取的試題之加權平均鑑別度(被選取的試題之鑑別度總和除以期望測驗時間最高界限和最低界限的平均) dtu = ，是表示被選取的試題組合之估計回答時間總和，超過期望測驗時間最高界限的差距值， ipt_u 為使用者對試卷測驗時間超過期望測驗時間最高界限所定義的處罰權重 2018/9/19

43 DRAT的試題配置基因演算法 (3/5) 3.物競天擇(Selection)
計算各染色體的適配值 v(Sk)，k = 1,2, … , pop_size + offspring_size 加總所有染色體Sk的適配值和選取機率 　　　　Pk = v(Sk) / V 計算各染色體Sk的累積選取機率 使用適配函數求出各染色體的適配值，根據各適配值的比例分配，採用俄羅斯輪盤選擇的方法，按照染色體適配值比例分配隨機選擇，來產生新的母體 產生一個範圍介於0到1之間的亂數r，設q０等於0，索引值為k，1 ≤ k ≤ pop_size + offspring_size，當qk-1 < r ≤ qk時，選擇第k個染色體Sk。 2018/9/19

44 DRAT的試題配置基因演算法 (4/5) 4.交配(Crossover) A[1110011001] A’[1110011011]
　　　　　　B[ ] 　　　　 B’[ ] Cut point Procedure: crossover Begin k = 0 while (k ≤ c / 2) do flag = 0 while flag = 0 do Generate random numbers R1 and R2 from discrete interval [1,K]. If R1 ≠ R2 then flag=1 end while crossover function(R1,R2) End 交配是使用一個切割點的方法(one-cut-point method)，它是從染色體中隨機選擇一個切割點，和另一個染色體交換切割點右邊的基因組，來產生二個新的子代。 程序中變數c表示交配步驟所要產生的子代染色體個數。隨機變數R1和R2是一個範圍值介於1到K的亂數，來隨機選擇要進行交配的兩個染色體。 2018/9/19

45 DRAT的試題配置基因演算法 (5/5) 5.突變(Mutation) A[1110011001] A’[1110011011]
　P = ( 1 / n ) Procedure: mutation Begin for(i=1, i ≤ nk, i++){ Generate random number yi from discrete interval [0, 1]. Mutation function(P, yi) } End 突變是指以突變機率來決定改變一個或多個染色體的基因值，當被選中的基因，基因值為1時，則突變成0，該試題由被選取狀態，變成不選取狀態；反之，則0突變成1，該試題由不選取狀態，變成被選取狀態。 突變機率的設定為P = ( 1 / n ) / e，e表示期望突變頻率，( 1 / n )表示因為一個染色體中期望只突變一個基因； 首先我們需要先產生一組範圍介於0到1的隨機變數y1, y2…, ynk，當該隨機變數小於P時，該隨機變數所代表的基因則進行突變 重覆2~5步驟，直到連續10代解無進步或已產生了1500代 2018/9/19

46 固定題數的試題配置問題 (FNTI) FNTI目標函式： FNTI限制式： x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
　　Maximize Z = FNTI限制式： 　　 x1 ≥ 1 xi+1 > xi , 1 ≤ i ≤ q_num – 1 xq_num ≤ n 　　 12 18 9 45 82 6 2 34 65 71 有時教學者會以固定題數為測驗的主要考量，以方便配分，我們將此問題稱為「固定題數的試題配置問題」(Fixed Number of Test Items Problem)，簡稱FNTI問題。 決策變數: xi 是一個正整數值的變數，它的範圍值如：1 ≤ xi ≤ n, i = 1 ~ q_num，表示第xi試題被選取； 參數 q_num：測驗試卷中的試題數量； 參數 di：試題Qi的鑑別度； 參數 rij：試題Qi對概念Cj的相關程度； 參數 m：測驗試卷概念個數； 參數 h：期望試題相關概念Cj的最低界限[h = ( q_num / m ) -使用者定義參數值]； 正整數變數xi　表示在試題配置結果中，被選取的試題編號，如：xi等於135，則表示Q135試題被選取。 限制式(4)表示，被選取出的所有試題與各概念間的相關程度總和不可低於期望相關程度，以使試卷的測驗概念能符合出題方向。 限制式(5)(6)(7)表示，為防止試卷中有二題相同的試題，造成重覆出題所設的限制。 在目標函式Z中，q_num表示需選取的試題數量，yyyyyy是指被選取出q_num題的試題鑑別度總和。 選取一定數量的試題 2018/9/19

47 FNTI的試題配置基因演算法 (1/5) 試題數目先決基因演算法 (Feasible Item First Genetic approach – FIFG) FIFG的進行步驟 1.建立母體 X 為染色體，包含有 q_num 個基因 X = [x1 , x2 , …, xq_num] 　X = [25, 118, …., 803] 基因值代表著一題試題的編號 xi ≠ xj ，且 i ≠ j 和 1 ≤ i, j ≤ q_num 為了處理固定題數的試題配置問題(Fixed Number of Test Items - FNTI)問題，我們提出一個試題數目先決基因演算法(Feasible Item First Genetic approach - FIFG)來解決 設變數X為母體中的染色體，包含有q_num個基因變數，X = [x1, x2, …, xq_num]； S表示一個集合，該集合中包含母體全部的染色體；K是表示母體中染色體的數量； Sk指母體S中第k個染色體。 首先隨機產生一組用正整數表示的各組試題序列，例如X =[25, 908, …., 113]，每個基因中的整數值代表著一題試題的編號，需注意的是xi　≠ xj ，而且 i ≠ j 和 1 ≤ i, j ≤ q_num，因為每個染色體當中不可包含相同的整數值，否則會有重覆出題的情況發生。 2018/9/19

48 FNTI的試題配置基因演算法 (2/5) 2.適配等級(Fitness ranking) R = dc  ipt dc =
適配函數　v(Sk) = 我們利用適配函數(fitness function)來計算染色體的適配值，當適配值愈高的染色體，愈能符合我們所設定的目標函式和限制條件，在演化(Evolution)的過程中經篩選(selection)後留下的機會也愈大，進而再繼續交配、繁衍和篩選，如此重覆終而演化成最符合要求的試題配置組合。我們為了讓染色體在基因演算法運算時，能夠快速的演化，所以在適配函數中加入使用處罰方法，加速適配值的收斂。 為了讓被選取的所有試題與各概念間的相關程度總和不可低於期望相關程度，以使試卷的測驗概念能符合出題方向，讓低於期望相關程度的試題配置組合獲得較低的適配值。所以我們定義一個處罰函數，以在求解過程中讓結果接近符合所設定的限制式 處罰函數定義為R = dc  ipt， R為針對試題組合的概念總和低於期望相關程度的處罰分數 dc = ，表示被選取的試題與各概念間的相關程度，其中低於期望相關程度的概念差距總和 ipt 為使用者對概念相關程度所定義的處罰權重 2018/9/19

49 FNTI的試題配置基因演算法 (3/5) 3.物競天擇(Selection)
計算各染色體的適配值 v(Sk)，k = 1,2, … , pop_size + offspring_size 加總所有染色體Sk的適配值和選取機率 　　　　Pk = v(Sk) / V 計算各染色體Sk的累積選取機率 使用適配函數求出各染色體的適配值，根據各適配值的比例分配，採用俄羅斯輪盤選擇的方法，按照染色體適配值比例分配隨機選擇，來產生新的母體 產生一個範圍介於0到1之間的亂數r，設q０等於0，索引值為k，1 ≤ k ≤ pop_size + offspring_size，當qk-1 < r ≤ qk時，選擇第k個染色體Sk。 2018/9/19

50 FNTI的試題配置基因演算法 (4/5) 4.交配(Crossover) 有兩相同基因值時，隨機更換其中一值，直到沒有相同基因值為止
　　A[12,15, 96,112,193,243]　　 A’[12,15,96,185,256,356] 　　B[3,56,108,185,256,356]　　 B’[3,56,108,112,193,243] 有兩相同基因值時，隨機更換其中一值，直到沒有相同基因值為止 試卷中不可有二題相同的試題 Cut point 交配是使用一個切割點的方法(one-cut-point method)，它是從染色體中隨機選擇一個切割點，和另一個染色體交換切割點右邊的基因組，來產生二個新的子代。 程序中變數c表示交配步驟所要產生的子代染色體個數。隨機變數R1和R2是一個範圍值介於1到K的亂數，來隨機選擇要進行交配的兩個染色體 如果進行交配操作後，一個染色體中包含兩個相同值的基因時，需進行隨機更換其中一個基因值，直到該染色體中沒有相同值的基因為止，以防止試卷中有二題相同的試題 2018/9/19

51 FNTI的試題配置基因演算法 (5/5) 5.突變(Mutation)
　 A[3,8,56,66,256,515] 　　A’[3,8,56,66,346,515] 　P = ( 1 / n ) Procedure: mutation Begin for (m = 1, m ≤ q_num  k, m++){ Generate random number rm from discrete interval [0, 1] Generate random number RC from discrete interval [1, n] mutation function(P, rm, RC) } End 突變是指以突變機率來決定改變一個或多個染色體的基因值，當被選中的基因，將其基因值突變成另一介於1到n的隨機值，表示該編號試題被選取，而原試題不選取。 突變機率的設定為P = ( 1 / q_num ) / e，e表示期望突變頻率，( 1 / q_num )表示因為一個染色體中期望只突變一個基因; 首先我們需要先產生一組範圍介於0到1隨機變數rm (m = 1,…, q_num  k)， RC是一個範圍從1到n的隨機變數，當rm小於P時，用來取代第m個基因的值，若RC和該染色體中的基因值有相同時，則需重新進行隨機取數，直到RC沒和該染色體有相同的基因值，以防止試卷中有二題相同的試題 重覆2~5步驟，直到連續10代解無進步或已產生了1500代 2018/9/19

52 試題參數調整演算法 鑑別度 難度 由試題配置演算法求出產生符合多目標試題配置的試卷，經由學習者學習測驗過後，試卷中的試題，其鑑別度和難度都將產生變異，在沒有適時適當的回饋調整時，將會造成試題鑑別度和難度無法充份精確表示，形成誤差，若再經由試題配置演算法產生成試卷後，週而復始，誤差將會愈來愈大，也就再要無法準確的診斷出學習者的學習障礙；所以針對這個問題，我們提出測驗結果回饋演算法( Test Result Feed Back Approach )，適時適當的回饋調整試題的鑑別度和難度，以保持試題鑑別度和難度的精確性。 學習者學習測驗過後，將學習者測驗成績、答案結果資料進行統計分析。當試卷測驗日期過後，系統模組會自動將該試卷所有的測驗結果，依各試題區分，取出高分組和低分組，根據測驗結果回饋演算法，計算出該試卷中各試題的鑑別度和難度，再以權重方式計算修改試題題庫中該試題的鑑別度和難度，以保持試題鑑別度和難度的精確性。另外再根據學習者的測驗成績和測驗歷程資料，列出統計數據和圖表，方便教學者查看或改善教學方式 D：試題鑑别度，它的範圍值為0~1； P：試題難度，它的範圍值為0~1； SH：高分組分數總合(全部測驗的分數排序取前高分的25%)； SL：低分組分數總合(全部測驗的分數排序取後低分的25%)； N：取測量人數的25%； Xmax：本題最高分； Xmin：本題最低分； 2018/9/19

53 實驗題庫樣本資料 每一個情況進行二十次實驗處理後，採用平均求解時間和平均鑑別度建立 實驗樣本 Item Bank N
Loading time (second) Average Discrimination 1 25 5.067 2 30 5.308 3 40 5.217 4 250 8.522 5 500 8.703 6 1000 13.599 7 2000 28.361 8 4000 60.887 為了評估我們所提出的CLFG和FIFG演算法的執行效率和求解結果的表現，我們施行了兩個實驗來比較CLFG、FIFG、隨機選取和Exhaustive Search等四種探索解答策略方法(Solution- seeking)的執行時間和鑑別度結果。 根據CLFG和FIFG演算法，針對每一個情況進行二十次實驗處理後，採用實驗結果的平均求解時間和平均鑑別度來建立這些統計資料 實驗中使用了八個不同的試題題庫，表6.1表示所使用的八個試卷題庫之特徵描述， 其中Item Bank代表不同的題庫編號， N代表題庫內的候選試題數量， Loading time代表從題庫中取出試題資料到系統記憶體，提供試題配置演算法運算的載入時間， Average Discrimination代表題庫中所有候選試題的平均鑑別度 2018/9/19

54 CLFG實驗結果及分析 (1/3) l = 30 N CLFG Random Selection Optimum Solution
Time(sec) Discrimination Time(min) 25 0.03 5 30 187 40 163840 250 >106 N/A 500 1000 2000 4000 表6.2、表6.3和表6.4分別指出期望測驗時間的最低界限設定在30分鐘、60分鐘和120分鐘時， CLFG、隨機選取和Exhaustive Search的花費時間和鑑別度的實驗結果比較。 由這些實驗中，可以看出多數的情況，用Exhaustive Search取得最佳解是最消耗時間的。 在N=30和l=60時，它就要花費幾乎三小時的時間(187分鐘)來搜尋最佳解，如此長的處理時間，實際應用上是明顯的不被接受的； 當N和l的值增加時，它變得非常不可能在一個可接受的合理時間範圍內搜尋到最佳解，這樣的情況刺激實際應用上的需求，為了求出一定品質水準 上的近似解，所以需要來設計heuristic algorithms來解決這樣的情況。 2018/9/19

55 CLFG實驗結果及分析 (2/3) l = 60 N CLFG Random Selection Optimum Solution
Time(sec) Discrimination Time(min) 30 0.03 187 40 163840 250 >106 N/A 500 1000 2000 4000 表6.2、表6.3和表6.4分別指出期望測驗時間的最低界限設定在30分鐘、60分鐘和120分鐘時， CLFG、隨機選取和Exhaustive Search的花費時間和鑑別度的實驗結果比較。 由這些實驗中，可以看出多數的情況，用Exhaustive Search取得最佳解是最消耗時間的。 在N=30和l=60時，它就要花費幾乎三小時的時間(187分鐘)來搜尋最佳解，如此長的處理時間，實際應用上是明顯的不被接受的； 當N和l的值增加時，它變得非常不可能在一個可接受的合理時間範圍內搜尋到最佳解，這樣的情況刺激實際應用上的需求，為了求出一定品質水準 上的近似解，所以需要來設計heuristic algorithms來解決這樣的情況。 2018/9/19

56 CLFG實驗結果及分析 (3/3) l = 120 N CLFG Random Selection Optimum Solution
Time(sec) Discrimination Time(min) 250 0.03 >106 N/A 500 1000 2000 4000 表6.2、表6.3和表6.4分別指出期望測驗時間的最低界限設定在30分鐘、60分鐘和120分鐘時， CLFG、隨機選取和Exhaustive Search的花費時間和鑑別度的實驗結果比較。 由這些實驗中，可以看出多數的情況，用Exhaustive Search取得最佳解是最消耗時間的。 在N=30和l=60時，它就要花費幾乎三小時的時間(187分鐘)來搜尋最佳解，如此長的處理時間，實際應用上是明顯的不被接受的； 當N和l的值增加時，它變得非常不可能在一個可接受的合理時間範圍內搜尋到最佳解，這樣的情況刺激實際應用上的需求，為了求出一定品質水準 上的近似解，所以需要來設計heuristic algorithms來解決這樣的情況。 2018/9/19

57 CLFG與最佳解的實驗數據圖表 (1/2) l = 30
圖6.4和圖6.5描述，關於CLFG和Exhaustive Search搜尋最佳解所需花費的求解時間比較。 當題庫內的候選試題數量超過40題後，Exhaustive Search已經是幾乎不太可能在合理時間範圍內找到最佳解， 而CLFG可以在非常短的時間內找到近似最佳解(少於一分鐘內) 2018/9/19

58 CLFG與最佳解的實驗數據圖表 (2/2) l = 60
圖6.4和圖6.5描述，關於CLFG和Exhaustive Search搜尋最佳解所需花費的求解時間比較。 當題庫內的候選試題數量超過40題後，Exhaustive Search已經是幾乎不太可能在合理時間範圍內找到最佳解， 而CLFG可以在非常短的時間內找到近似最佳解(少於一分鐘內) 2018/9/19

59 CLFG在不同測驗時間下限的試題配置 根據統計資料表示CLFG的處理時間長短與候選試題數量和被選取的所有試題所需花費期望測驗時間的最低界限有直接的比例關係。 CLFG能夠快速處理2,500題內的候選試題，但當候選試題數量超過2,500時，CLFG的處理時間會相對大大地提高， 但處理時間仍在合理可接受的時間範圍內(少於一分鐘內)。 2018/9/19