Microsoft Word - 第15章 人工智慧.doc

Transcription

1 第 5 章 人 工 智 慧 人 工 智 慧 的 研 究 起 源 甚 早,943 年 McCulloch 和 Pitts 即 開 始 從 事 神 經 系 統 之 研 究 而 嘗 試 建 構 神 經 運 作 之 模 型 人 工 智 慧 (Artificial Intelligence, 簡 稱 AI) 一 詞 係 於 956 年 由 McCarthy 教 授 所 提 出 ; 自 此, 人 工 智 慧 的 研 究 即 蓬 勃 發 展 [Negnevitsky2002] 國 內 人 工 智 慧 的 前 輩 孫 家 麟 教 授 曾 指 出 :intelligence 乃 是 由 拉 丁 文 legere 演 變 而 來, 本 意 是 蒐 集 和 組 合, 並 從 事 選 擇 進 而 能 瞭 解 和 感 受 人 類 若 能 製 造 出 一 種 能 夠 蒐 集 組 合 進 而 選 擇 瞭 解 和 感 受 的 機 器 來, 我 們 就 有 了 人 工 智 慧 [ 孫 家 麟 985] 人 工 智 慧 的 研 究 領 域 涵 蓋 甚 廣, 其 著 稱 者 包 含 : 電 腦 遊 戲 (computer game) 專 家 系 統 (expert systems) 自 然 語 言 處 理 (natural language processing) 模 式 識 別 (pattern recognition) 電 腦 視 覺 (computer vision) 機 械 學 習 (machine learning) 模 糊 理 論 (fuzzy theory) 基 因 演 算 法 (genetic algorithms) 類 神 經 網 路 (artificial neural networks) 資 料 採 掘 (data mining) 智 慧 型 代 理 人 (intelligent agents) 機 器 人 (robotics) 等 本 章 的 主 要 目 的 是 藉 由 一 些 有 趣 的 問 題, 引 導 讀 者 瞭 解 人 工 智 慧 是 如 何 來 解 決 各 種 問 題, 進 而 引 發 讀 者 對 人 工 智 慧 研 究 的 興 趣 5- 解 決 困 難 問 題 困 難 問 題 (puzzles) 是 需 要 智 慧 來 解 決 的 因 此, 解 決 難 題 早 期 被 視 為 是 人 工 智 慧 中 一 個 重 要 的 研 究 課 題 例 如 : 有 一 個 人 帶 著 一 隻 狼 一 隻 羊 與 一 粒 甘 藍 在 河 的 左 岸 想 要 渡 河, 岸 邊 有 一 艘 船 只 能 容 納 一 人 與 一 物 然 而, 若 人 不 在 其 旁, 則 狼 會 吃 掉 羊 ; 相 同 的, 羊 會 吃 掉 甘 藍 請 問 : 這 個 人 有 可 能 帶 著 他 的 財 產 安 全 地 渡 河 嗎? [Hopcroft979]

2 對 於 上 述 問 題, 我 們 可 用 M W G 和 C 分 別 代 表 人 狼 羊 和 甘 藍 由 MWGC 四 個 符 號, 可 以 形 成 6 種 不 同 組 合 亦 即 :MWGC MWG MWC MGC WGC MW MG MC WG WC GC M W G C 和 ( 空 集 合 ) 我 們 以 短 線 - 代 表 河, 短 線 的 左 邊 代 表 左 岸, 右 邊 代 表 右 岸 例 如,WC-MG 表 示 目 前 的 狀 態 (state) 是 : 在 河 的 左 岸 有 狼 和 甘 藍, 右 岸 則 有 人 和 羊 剛 開 始 時, 人 狼 羊 和 甘 藍 都 在 河 的 左 岸, 所 以 起 始 狀 態 (initial state) 為 MWGC- 題 意 是 希 望 人 能 想 出 一 個 方 法, 帶 著 狼 羊 和 甘 藍 安 全 地 渡 河 到 右 岸, 所 以 終 止 狀 態 (final state) 應 為 -MWGC 從 起 始 狀 態 開 始 分 析, 人 可 帶 著 其 中 一 物 或 是 不 帶 任 何 一 物 渡 河, 因 此, 下 一 個 可 能 的 狀 態 有 下 列 四 種 : GC-MW: 此 人 帶 著 狼 渡 河 到 右 岸, 左 岸 則 留 下 羊 與 甘 藍 根 據 題 意, 此 時 羊 會 吃 掉 甘 藍, 所 以 這 個 狀 態 是 不 安 全 的 WG-MC: 此 人 帶 著 甘 藍 渡 河 到 右 岸, 左 岸 留 下 狼 與 羊 此 時 狼 會 吃 掉 羊, 所 以 這 個 狀 態 也 是 不 安 全 的 WC-MG: 此 人 帶 著 羊 渡 河 到 右 岸, 左 岸 留 下 狼 與 甘 藍 此 時 羊 與 甘 藍 都 不 會 被 吃 掉, 所 以 這 個 狀 態 是 安 全 的 WGC-M: 此 人 獨 自 渡 河 到 右 岸, 左 岸 留 下 狼 羊 與 甘 藍 此 時, 甘 藍 可 能 被 羊 吃 掉, 或 羊 被 狼 吃 掉, 所 以 這 個 狀 態 也 是 不 安 全 的 根 據 以 上 的 分 析,WC-MG 是 唯 一 安 全 的 狀 態, 我 們 可 以 從 此 一 安 全 狀 態 繼 續 渡 河 此 時, 下 一 個 狀 態 又 有 下 列 兩 種 可 能 : MWGC- : 此 人 又 帶 著 羊 回 到 左 岸, 與 起 始 狀 態 一 樣, 因 此 形 成 一 個 迴 圈 若 是 一 直 繞 著 這 個 迴 圈 渡 河, 那 麼 問 題 就 無 法 解 決 MWC-G: 此 人 獨 自 回 到 左 岸, 將 羊 單 獨 留 在 右 岸 此 時 羊 與 甘 藍 都 不 會 被 吃 掉, 所 以 這 個 狀 態 是 安 全 的 2

3 繼 續 以 上 的 分 析, 我 們 可 以 得 到 如 圖 5- 的 狀 態 轉 變 圖 (state transition diagram), 其 中 以 橢 圓 表 示 狀 態, 狀 態 之 間 以 箭 頭 連 接, 表 示 從 一 個 狀 態 轉 變 到 另 一 個 狀 態, 箭 號 上 標 示 有 w g 或 c, 表 示 此 人 帶 著 狼 羊 或 甘 藍 渡 河, 若 為 m, 表 示 此 人 單 獨 渡 河 起 始 狀 態 以 Start 箭 頭 表 示, 最 後 終 止 狀 態 以 雙 圈 表 示 由 圖 5- 可 得 知, 從 起 始 狀 態 到 終 止 狀 態 間 有 路 可 行, 表 示 此 人 可 以 從 左 岸 帶 著 他 的 狼 羊 與 甘 藍 安 全 地 渡 河 到 右 岸, 整 條 路 徑 即 表 示 其 渡 河 的 過 程 Start MWGC- g g WC-MG m m MWC-G w w c c C-MWG W-MGC g g g g MGC-W MWG-C c c w w -MWGC g g MG-WC m m G-MWC 圖 5- 人 狼 羊 與 甘 藍 問 題 的 狀 態 轉 變 圖 5-2 電 腦 遊 戲 下 圍 棋 象 棋 或 西 洋 棋 等, 都 是 需 要 高 度 智 慧 的, 所 以 電 腦 遊 戲 (computer game) 也 是 人 工 智 慧 中 一 項 相 當 吸 引 人 的 研 究 997 年,IBM 的 超 級 電 腦 深 藍 打 敗 西 洋 棋 王, 令 人 工 智 慧 研 究 者 相 當 振 奮 [DeepBlue2005] 在 本 節 我 們 以 簡 單 的 井 字 遊 戲 (Tic-Tac-Toe) 來 說 明 人 工 智 慧 如 何 來 分 析 電 腦 遊 戲 [Nilsson998] 3

4 井 字 遊 戲 是 雙 人 玩 的, 在 畫 有 井 " 字 的 九 個 空 格 裡, 一 方 畫, 一 方 畫 畫 的 一 方 先 下, 誰 先 完 成 一 列 一 行 或 對 角 線, 誰 就 贏 在 一 般 雙 人 對 奕 的 棋 戲 中, 人 工 智 慧 大 都 採 用 極 大 極 小 法 (minimaxing method) 來 評 估 下 一 步 棋 應 如 何 走 極 大 極 小 法 是 以 目 前 的 盤 局, 考 慮 所 有 可 能 可 以 走 的 棋 步 ; 對 於 每 一 個 可 能 的 新 盤 局, 也 考 慮 所 有 可 能 可 以 走 的 棋 步 ; 如 是 一 直 推 衍 下 去, 可 以 考 量 到 很 多 步 之 後 所 有 可 能 的 盤 局 當 然, 考 量 的 棋 步 越 多, 勝 算 也 就 越 大, 然 而 計 算 量 也 隨 著 激 增 我 們 需 要 設 計 一 個 評 估 函 數 (evaluation function) 來 評 估 每 一 個 盤 局 對 雙 方 的 勝 算 如 何 假 設 畫 的 一 方 定 為 極 大 (MA), 畫 的 一 方 定 為 極 小 (MIN), 那 麼 在 設 計 評 估 函 數 時, 所 得 到 的 數 值 如 果 越 大, 表 示 對 的 一 方 就 越 有 利 ; 相 反 的, 如 果 評 估 函 數 所 得 到 的 數 值 越 小, 表 示 對 的 一 方 就 越 有 利 此 種 設 計 有 一 前 提, 那 就 是 假 設 雙 方 都 會 朝 向 對 自 己 有 利 的 棋 步 走 (a) (b) (c) 圖 5-2 盤 局 評 估 函 數 的 計 算 對 於 井 字 遊 戲, 假 設 目 前 考 慮 的 盤 局 為 p, 我 們 可 以 設 計 一 個 簡 單 的 評 估 函 數 e(p) 如 下 : 假 如 盤 局 p 仍 無 法 分 出 勝 負, 則 e(p) =(MA 仍 有 可 能 完 成 的 行 數 列 數 與 對 角 線 的 總 和 ) (MIN 仍 有 可 能 完 成 的 行 數 列 數 與 對 角 線 的 總 和 ) ( 此 處, 我 們 以 縱 向 為 行, 橫 向 為 列 ) 假 如 於 盤 局 p 獲 勝 一 方 已 確 定 為 MA, 則 e(p) = ; 相 反 的, 假 如 於 盤 局 p 獲 勝 一 方 已 確 定 為 MIN, 則 e(p) = 因 此, 假 若 盤 局 p 如 圖 5-2(a) 所 示, 其 評 估 函 數 值 e(p) = 6 4 = 2 因 為 對 MA( 即 的 一 方 ) 而 言, 尚 有 可 能 完 成 第 一 行 或 第 三 行, 第 二 列 或 第 三 列, 還 有 兩 條 對 角 線, 合 起 來 共 有 6 種 可 能 完 成 的 連 線, 如 圖 5-2(b) 所 示 同 理, 對 MIN( 即 的 一 方 ) 而 言, 只 有 4 種 可 能 完 成 的 連 線, 如 圖 5-2(c) 所 示 4

5 為 了 要 減 少 盤 局 的 個 數, 以 減 少 評 估 函 數 的 計 算, 對 稱 的 盤 局 都 視 為 相 同 例 如 : 圖 5-3 中 的 4 個 盤 局 都 視 為 相 同, 因 為 盤 局 (b) (c) 與 (d) 分 別 以 所 畫 虛 線 而 與 盤 局 (a) 相 對 稱 (a) (b) (c) (d) 圖 5-3 對 稱 的 盤 局 A MA s move B E F 6 4 = = C = = = 4 5 = 5 5 = = = D 6 5 = 5 5 = = 圖 5-4 井 字 遊 戲 前 兩 步 所 有 盤 局 形 成 一 樹 狀 結 構 在 圖 5-4, 我 們 從 空 白 的 棋 盤 開 始, 考 量 下 前 兩 步 所 有 可 能 的 盤 局, 評 估 函 數 值 就 列 在 其 右 MA 由 空 白 的 盤 局 A 開 始 先 走 一 步, 可 能 成 為 盤 局 B C 或 5

6 D 若 為 盤 局 B, 改 由 MIN 走 下 一 步, 可 能 成 為 盤 局 E 或 F, 其 評 估 函 數 值 分 別 為 2 和 對 MIN 而 言, 選 擇 有 較 小 評 估 函 數 值 的 盤 局 對 其 較 為 有 利 因 此, 盤 局 B 的 評 估 值 為 同 理, 盤 局 C 和 D 的 評 估 值 分 別 為 2 和 最 後,MA 從 盤 局 B C 和 D 中 選 取 有 較 大 的 評 估 值 對 其 較 為 有 利 因 為 盤 局 B 的 評 估 值 最 大, 故 而 盤 局 A 的 評 估 值 為, 意 即 MA 走 一 步 到 盤 局 B 的 勝 算 最 大 對 於 MA 或 是 MIN 任 何 一 方 有 利 的 棋 步 分 數 ( 即 評 估 值 ), 我 們 以 圓 圈 將 其 圈 起 來 假 設 MA 根 據 上 述 評 估, 畫 了 於 井 字 的 中 間 ( 即 盤 局 B), 並 且 MIN 在 的 左 邊 畫 了 來 回 應 ( 這 一 步 對 MIN 來 說 並 不 是 好 步 ) 接 著 MA 又 往 下 考 慮 了 兩 步, 得 到 如 圖 5-5 的 結 果 0 A D 0 MA s move C 4 3 = B C 4 2 = = = = 4 3 = E 4 2 = = 3 2 = 3 2 = 3 3 = = = 5 3 = = = = = = 4 3 = 4 2 = 2 圖 5-5 井 字 遊 戲 MA 一 方 第 二 次 考 量 6

7 此 時, 有 兩 個 棋 步 ( 圖 5-5 中 的 盤 局 C 和 E) 都 得 到 相 同 的 最 好 評 估 值 ( 其 值 為 ) 假 設 MA 如 圖 所 標 示, 走 到 盤 局 C 此 時,MIN 為 了 要 避 免 立 即 的 危 險, 他 會 在 左 上 角 畫 上, 得 到 盤 局 C MA 繼 續 再 往 下 考 慮 兩 步, 得 到 如 圖 5-6 的 結 果 MA 的 下 一 步, 盤 局 B C D 和 E 的 評 估 值 均 為, 表 示 這 些 棋 步 可 能 會 讓 MIN 立 即 贏 了 這 盤 棋 唯 獨 盤 局 F 的 評 估 值 為, 表 示 還 有 勝 算 聰 明 的 你 應 該 知 道, 要 畫 在 哪 裡 可 以 獲 勝 B 2 = 2 = 2 = C 3 = 2 3 = 2 2 = 3 2 = A D 2 2 = = 0 MA s move F E 3 = 2 2 = 3 = 2 2 = 3 2 = 2 2 = = 圖 5-6 井 字 遊 戲 MA 一 方 第 三 次 考 量 7

8 5-3 專 家 系 統 專 家 系 統 可 算 是 在 970 年 代 人 工 智 慧 研 究 中, 最 為 成 功 也 是 應 用 最 為 廣 泛 的 領 域 如 圖 5-7 所 示, 一 個 專 家 系 統 基 本 上 包 含 有 知 識 庫 (knowledge base) 與 推 論 機 制 (inference engine) 等 兩 個 部 分 知 識 庫 內 儲 存 著 某 一 知 識 範 疇 內 的 專 家 知 識 (expertise), 並 以 某 種 知 識 表 達 法 (knowledge representation) 來 表 示 當 使 用 者 輸 入 一 些 已 知 的 事 實 (facts) 後, 推 論 機 制 就 以 知 識 庫 內 的 專 家 知 識 和 所 輸 入 的 事 實, 依 據 數 學 邏 輯 推 導 出 結 論, 並 告 知 使 用 者 使 用 者 事 實 結 論 知 識 庫 推 論 機 制 專 家 系 統 圖 5-7 專 家 系 統 基 本 概 念 早 期 著 名 的 專 家 系 統 有 疾 病 診 斷 的 MYCIN 系 統, 由 光 譜 來 分 析 化 學 成 分 的 DENDRAL 系 統, 分 析 地 質 資 料 以 探 勘 石 油 的 DIPMETER 系 統 以 及 探 勘 礦 藏 的 PRSPECTR 系 統, 和 電 腦 系 統 組 合 的 CN/R 系 統 其 中 以 MYCIN 系 統 最 為 著 名 且 最 重 要, 其 原 因 有 三 :() 它 證 實 了 人 工 智 慧 可 以 被 用 來 解 決 真 實 世 界 中 實 際 的 問 題 ;(2) 它 提 供 了 一 個 測 試 平 台 以 測 試 一 些 新 的 觀 念, 例 如 : 解 釋 自 動 擷 取 知 識 和 智 慧 型 教 學 等 功 能 ;(3) 它 展 示 了 專 家 系 統 骨 架 (shell) 的 實 用 性, 可 更 簡 易 地 建 構 一 個 專 家 系 統 [Giarratano2004] 知 識 表 達 法 最 常 用 到 的 也 是 最 簡 單 的 方 式 為 規 則 (rules), 其 形 式 如 下 : If 前 提 前 提 2 前 提 n Then 結 論 結 論 2 結 論 m 8

9 其 中,n 和 m 均 大 於 0 規 則 也 可 以 用 圖 形 方 式 表 示, 如 圖 5-8 所 示 其 中, 前 提 (antecedents) 部 分 包 含 規 則 成 立 的 條 件, 它 可 為 已 知 的 事 實 或 是 其 它 規 則 的 結 論 (consequents) 對 於 以 規 則 方 式 表 達 的 知 識 而 言, 其 推 論 方 式 可 分 為 兩 種 : 一 種 是 前 向 鍊 結 (forward chaining), 另 一 種 是 後 向 鍊 結 (backward chaining) 前 向 鍊 結 是 依 據 已 知 的 事 實 與 先 前 所 推 導 出 的 結 論, 檢 視 是 否 符 合 某 規 則 的 前 提 部 分, 若 符 合 則 可 推 得 結 論 ; 一 般 用 於 從 觀 察 到 的 事 實 中 推 導 出 可 能 的 結 論 至 於 後 向 鍊 結 則 是 由 結 論 開 始 反 推 回 去, 透 過 規 則 得 知 需 要 哪 些 前 提, 才 能 推 得 結 論 ; 一 般 用 於 查 詢 (queries) 時 使 用 前 提 前 提 2 前 提 n 結 論 結 論 2 結 論 m 圖 5-8 規 則 的 圖 形 表 示 法 舉 例 來 說, 假 設 我 們 有 下 列 規 則 : If?x 是 肉 食 性 動 物?x 是 金 黃 色?x 有 黑 色 條 紋 Then?x 是 老 虎 其 中,?x 為 一 變 數, 可 以 代 入 任 何 值 此 規 則 意 為 : 有 一 動 物, 若 滿 足 三 項 條 件 : 肉 食 性 動 物, 金 黃 色, 且 有 黑 色 條 紋, 則 可 推 論 得 知 出 : 牠 是 老 虎 假 若 我 們 已 知 有 一 隻 動 物 名 叫 阿 丹, 牠 滿 足 上 列 三 項 條 件, 根 據 前 向 鍊 結, 我 們 可 以 推 得 : 阿 丹 是 一 隻 老 虎 假 若 我 們 要 問 : 阿 丹 是 否 為 一 隻 老 虎? 根 據 後 向 鍊 結, 我 們 必 須 要 進 一 步 檢 視 看 看, 目 前 已 知 的 事 實 與 所 推 導 出 來 的 結 論, 是 否 滿 足 前 提 部 分 的 三 項 條 件 9

10 Z: If?x 有 頭 髮 Then?x 是 哺 乳 類 動 物 Z2: If?x 會 產 奶 Then?x 是 哺 乳 類 動 物 Z3: If?x 有 羽 毛 Then?x 是 鳥 類 Z4: If?x 會 飛?x 會 生 蛋 Then?x 是 鳥 類 Z5: If?x 是 哺 乳 類 動 物?x 吃 肉 Then?x 是 肉 食 性 動 物 Z6: If?x 是 哺 乳 類 動 物?x 有 尖 銳 的 牙 齒?x 有 爪?x 有 銳 利 的 眼 睛 Then?x 是 肉 食 性 動 物 Z7: If?x 是 哺 乳 類 動 物?x 有 蹄 Then?x 是 有 蹄 類 動 物 Z8: If?x 是 哺 乳 類 動 物?x 會 反 芻 Then?x 是 有 蹄 類 動 物 Z9: If?x 是 肉 食 性 動 物?x 是 金 黃 色?x 有 深 色 斑 點 Then?x 是 豹 Z0: If?x 是 肉 食 性 動 物?x 是 金 黃 色?x 有 黑 色 條 紋 Then?x 是 老 虎 Z: If?x 是 有 蹄 類 動 物?x 有 長 腳?x 有 長 脖 子?x 是 金 黃 色?x 有 深 色 斑 點 Then?x 是 長 頸 鹿 Z2: If?x 是 有 蹄 類 動 物?x 是 白 色?x 有 黑 色 條 紋 Then?x 是 斑 馬 Z3: If?x 是 鳥 類?x 不 會 飛?x 有 長 腳?x 有 長 脖 子?x 是 黑 白 相 間 Then?x 是 鴕 鳥 Z4: If?x 是 鳥 類?x 不 會 飛?x 會 游 泳?x 是 黑 白 相 間 Then?x 是 企 鵝 Z5: If?x 是 鳥 類?x 很 會 飛 Then?x 是 信 天 翁 圖 5-9 羅 碧 所 使 用 辨 識 動 物 種 類 的 知 識 庫 假 設 有 個 機 器 人 名 叫 羅 碧, 要 到 動 物 園 去 參 觀 它 只 能 觀 察 到 動 物 簡 單 的 特 徵 (features), 例 如 : 顏 色 大 小 以 及 動 物 是 否 有 頭 髮 會 不 會 產 奶 等, 但 0

11 是 它 沒 有 足 夠 的 能 力 去 識 別 動 物 的 種 類 因 此, 我 們 可 以 商 請 生 物 學 家 來 幫 羅 碧 建 構 一 個 專 家 系 統, 使 它 能 夠 利 用 所 觀 察 到 的 基 本 特 徵 來 辨 識 動 物 的 種 類 假 設 動 物 園 內 只 有 七 種 動 物 : 虎 豹 長 頸 鹿 斑 馬 鴕 鳥 企 鵝 與 信 天 翁 此 專 家 系 統 以 規 則 的 方 式 來 建 構 其 知 識 庫, 其 中 包 含 有 十 五 條 規 則 Z 到 Z5, 如 圖 5-9 所 示, 並 利 用 前 向 鍊 結 的 推 論 機 制 來 辨 識 動 物 的 種 類 [Winston992] 假 設 羅 碧 看 到 一 隻 動 物 名 叫 小 葉, 有 如 下 特 徵 :() 有 頭 髮,(2) 會 反 芻, (3) 有 長 腳,(4) 有 長 脖 子,(5) 是 金 黃 色, 和 (6) 有 深 色 斑 點 因 為 小 葉 有 頭 髮, 根 據 規 則 Z, 我 們 可 以 得 知 : 小 葉 是 哺 乳 類 動 物 因 為 小 葉 是 哺 乳 類 動 物, 而 且 會 反 芻, 根 據 規 則 Z8, 可 以 推 論 得 知 : 小 葉 是 有 蹄 類 動 物 至 此, 規 則 Z 前 提 部 分 的 五 個 條 件 都 符 合, 最 後 可 以 得 知 : 小 葉 是 長 頸 鹿 整 個 推 論 過 程 可 以 用 圖 5-0 表 示, 其 中 黑 色 方 形 表 示 為 所 觀 察 到 的 特 徵, 白 色 方 形 為 經 過 前 向 鍊 結 所 推 得 的 結 論 有 頭 髮 Z 是 哺 乳 類 動 物 會 反 芻 Z8 有 蹄 類 動 物 有 長 腳 有 長 脖 子 Z 是 長 頸 鹿 是 金 黃 色 有 深 色 斑 點 圖 5-0 推 論 小 葉 是 長 頸 鹿 的 整 個 過 程

12 5-4 自 然 語 言 處 理 自 然 語 言 (natural languages) 指 的 是 人 類 所 使 用 的 語 言, 如 中 文 英 文 等, 用 以 區 別 電 腦 程 式 語 言 (computer programming languages), 如 C C++ Java 語 言 自 然 語 言 的 處 理 包 含 語 彙 (lexical) 分 析 語 法 (syntactical) 分 析 和 語 意 (semantic) 分 析 等 三 個 層 面 在 一 個 英 文 句 子 中, 語 彙 的 分 析 是 要 將 其 單 字 (words) 切 割 出 來 語 法 的 分 析 是 進 一 步 檢 視 單 字 的 順 序, 是 否 符 合 文 法 (grammar) 結 構, 而 語 意 的 分 析 則 更 進 一 步 嘗 試 了 解 句 子 的 意 義 (meaning) 假 設 我 們 要 分 析 Bill printed the file 這 個 句 子 在 英 文 中, 語 彙 分 析 較 為 簡 單, 因 為 英 文 單 字 都 用 空 白 或 標 點 符 號 隔 開, 所 以 要 切 割 單 字 出 來 就 比 較 容 易 上 述 例 句, 我 們 可 以 切 出 Bill printed the 和 file 四 個 單 字 至 於 語 法 的 分 析, 我 們 必 須 先 給 定 英 文 的 文 法 例 如 : 一 個 英 文 句 子 (sentence, 簡 稱 S) 可 以 由 名 詞 片 語 (noun phrase, 簡 稱 NP) 後 接 動 詞 片 語 (verb phrase, 簡 稱 VP) 所 組 成, 可 以 表 達 成 如 圖 5- 中 規 則 R 的 形 式 [Rich99] R: S NP VP R2: NP the NP R3: NP PR R4: NP PN R5: NP NP R6: NP ADJS N R7: ADJS ε ADJ ADJS R8: VP V R9: VP V NP R0: N file printer R: PN Bill R2: PR I R3: ADJ short long fast R4: V printed created want 圖 5- 部 分 英 文 文 法 2

13 同 理, 一 個 名 詞 片 語 可 以 是 定 冠 詞 the 後 接 另 一 個 新 名 詞 片 語 (NP) 或 是 代 名 詞 (pronoun, 簡 稱 PR) 或 是 專 有 名 詞 (proper noun, 簡 稱 PN) 或 是 新 名 詞 片 語 (NP), 其 規 則 為 R2 到 R5 而 新 名 詞 片 語 (NP) 則 是 由 形 容 詞 串 (adjectives, 簡 稱 ADJS) 後 接 名 詞 所 構 成, 其 規 則 為 R6 而 形 容 詞 串 則 可 以 不 包 含 任 何 形 容 詞 ( 以 ε 表 示 ), 或 是 由 形 容 詞 (adjective, 簡 稱 ADJ) 後 接 形 容 詞 串 (ADJS) 所 構 成, 其 規 則 為 R7, 其 中, 垂 直 線 ( ) 代 表 或 是 的 意 思 相 同 地, 動 詞 片 語 可 以 只 包 含 動 詞 (verb, 簡 稱 V), 或 是 由 動 詞 後 接 名 詞 片 語 所 組 成, 其 規 則 為 R8 和 R9 假 設 一 個 迷 你 字 典 中 包 含 有 名 詞 file 和 printer, 專 有 名 詞 Bill, 代 名 詞 I, 形 容 詞 short long 和 fast, 動 詞 則 有 printed created 和 want 等, 其 可 以 規 則 形 式 表 達 如 圖 5- 中 R0 到 R4 根 據 以 上 的 簡 單 英 文 文 法, 上 述 例 句 Bill printed the file 可 以 被 分 析 成 樹 狀 結 構, 稱 為 剖 析 樹 (parse tree), 如 圖 5-2 所 示 語 法 分 析 有 兩 種 方 式 : 由 上 而 下 剖 析 (top-down parsing) 和 由 下 而 上 剖 析 (bottom-up parsing) 由 上 而 下 的 語 法 分 析 是 從 句 子 (S) 開 始, 根 據 文 法 規 則, 由 其 箭 頭 右 邊 的 NP VP 所 取 代,NP 又 由 PN 所 取 代, 而 PN 為 Bill 所 取 代 ; 接 著 VP 由 V NP 所 取 代,V 為 printed 所 取 代,NP 為 the NP 所 取 代,NP 又 為 ADJS N 所 取 代, 而 ADJS 為 ε, 最 後 N 為 file 所 取 代 取 代 完 後 的 字 串 為 Bill printed the file, 剛 好 和 輸 入 例 句 一 樣, 所 以 語 法 剖 析 成 功, 代 表 語 法 正 確 S NP VP PN V NP Bill printed the NP ADJS ε N file 圖 5-2 例 句 Bill printed the file 的 剖 析 樹 3

14 由 下 而 上 的 剖 析 是 由 輸 入 的 句 子 開 始 分 析, 首 先 根 據 文 法,Bill 可 以 由 其 左 邊 的 PN 取 代,PN 又 由 NP 所 取 代 ; 接 著 printed 由 V 所 取 代,file 由 N 所 取 代, ε 由 ADJS 所 取 代 然 後,ADJS 和 N 由 NP 所 取 代, 接 著,the NP 又 由 NP 所 取 代, 再 來,V NP 又 由 VP 所 取 代, 最 後 NP VP 由 S 所 取 代 至 此, 整 個 句 子 剛 好 符 合 文 法 規 則 定 義, 代 表 句 子 的 文 法 無 誤 至 於 語 意 的 分 析 則 較 為 複 雜 與 困 難, 因 為 自 然 語 言 中 常 常 含 有 混 淆 不 清 的 語 意, 必 須 藉 由 前 後 文 (context) 才 能 確 定 真 正 的 意 義 例 如 : 英 文 句 子 I saw a man on the street, 其 中 介 詞 片 語 on the street 可 以 當 作 主 詞 補 語 或 受 詞 補 語 若 為 主 詞 I 的 補 語, 其 意 應 為 : 我 在 街 上 看 到 一 個 人 若 為 受 詞 a man 的 補 語, 其 意 應 為 : 我 看 到 一 個 人 在 街 上 如 何 知 道 介 詞 片 語 是 主 詞 補 語 或 是 受 詞 補 語, 必 須 由 前 後 文 才 能 判 知, 因 此 處 理 起 來 較 為 複 雜 在 早 期 的 自 然 語 言 處 理 中,ELIZA [Weizenbaum966] 是 一 個 非 常 有 名 的 程 式, 它 模 擬 心 理 治 療 家 Carl R. Rogers 的 精 神 治 療 法 當 使 用 者 輸 入 任 意 一 個 句 子, 電 腦 會 以 它 自 己 的 句 子 回 答, 如 圖 5-3(a) 所 示 為 使 用 者 與 ELIZA 的 部 分 對 話, 其 中 Person 代 表 使 用 者 輸 入 的 句 子, 而 ELIZA 代 表 電 腦 的 回 答 [ 孫 家 麟 985, Rich99] ELIZA 是 由 兩 個 部 分 所 組 成, 一 為 主 程 式, 另 一 部 分 Weizenbaum 視 之 為 腳 本 (script) 的 知 識 庫, 它 是 一 組 規 則 所 組 成, 圖 5-3(b) 為 ELIZA 的 部 分 規 則, 其 中,?x 和?y 為 變 數 假 若 我 們 有 E 和 E2 兩 條 規 則, 當 使 用 者 輸 入 句 子 My brother is smart,eliza 主 程 式 會 使 用 樣 板 比 對 (pattern matching) 技 巧 來 比 對 上 述 規 則 箭 號 左 邊 的 部 分 對 於 第 一 條 規 則,My 與 My 對 應,brother 屬 於 family-member, 也 可 以 對 應,is 與 is 對 應,smart 對 應 變 數?y 因 此, 變 數?y 的 值 變 成 為 smart 對 於 第 二 條 規 則,My 對 應 變 數?x,brother 對 應 family-member, 4

15 剩 下 的 句 子 is smart 對 應 變 數?y 以 上 輸 入 的 句 子, 可 以 成 功 地 匹 配 兩 條 規 則, 因 此 可 用 規 則 右 邊 的 句 子 回 答 Who else in your family is smart? 或 Tell me more about your family. 若 是 沒 有 可 以 比 對 的 規 則, 那 麼 有 一 些 預 設 的 句 子 可 用 來 回 答, 例 如 : Please go on. 或 I am not sure I understand you fully., 以 繼 續 交 談 Person: Men are all alike. ELIZA: In what way? Person: They re always bugging us about something or other. ELIZA: Can you think of a specific example? Person: Well, my boyfriend made me come here. ELIZA: Your boyfriend made you come here. Person: He says I m depressed much of the time. ELIZA: I am sorry to hear you are depressed. Person: It s true. I am unhappy. ELIZA: Do you think coming here will help you not to unhappy? Person: I need some help, that much seems certain. ELIZA: What would it mean to you if you got some help? Person: Perhaps I could learn to get along with my mother. ELIZA: Tell me more about your family. (a) 與 ELIZA 的 部 分 對 話 E: (My {family-member} is?y) (Who else in your family is?y) E2: (?x {family-member}?y) (Tell me more about your family) E3: (?x me?y) (?x you?y) E4: (I remember?x) (Why do remember?x just now?) (b) ELIZA 的 部 分 規 則 圖 5-3 與 ELIZA 的 部 分 對 話 與 部 分 規 則 5-5 機 械 學 習 機 械 學 習 (machine learning) 的 目 的 乃 在 模 擬 人 類 的 學 習 能 力 最 簡 單 的 學 習 即 是 背 誦, 將 所 要 學 習 的 事 物 記 下 來, 例 如 背 書 ; 此 類 學 習 可 用 資 料 庫 等 技 術 5

16 將 事 物 記 錄 下 來, 方 便 以 後 查 詢 進 階 的 學 習, 可 從 一 些 事 例 (cases) 中, 歸 納 出 經 驗 法 則, 此 為 人 類 智 慧 的 更 進 一 步 表 現 機 械 學 習 可 分 為 符 號 式 學 習 (symbolic learning) 和 連 結 式 學 習 (connectionist learning) 符 號 式 學 習 是 將 事 例 依 其 特 徵 以 文 字 或 符 號 方 式 表 示, 然 後 嘗 試 取 出 其 分 類 規 則 而 連 結 式 學 習 則 是 將 事 例 的 特 徵 用 數 值 形 式 表 示, 然 後 用 類 神 經 網 路 的 機 制 來 學 習 其 分 類 規 則 類 神 經 網 路 的 學 習 機 制 於 5-6 節 介 紹, 而 本 節 中 介 紹 符 號 式 學 習 機 制 假 設 你 到 海 灘 戲 水, 發 現 有 些 人 會 被 太 陽 曬 傷, 有 些 人 卻 不 會, 因 此 你 很 好 奇 地 想 去 研 究 : 造 成 曬 傷 的 原 因 是 什 麼? 於 是, 你 拿 起 筆 來, 簡 單 地 就 你 所 觀 察 到 的 一 些 特 徵 記 錄 下 來, 如 表 5- 所 示 所 觀 察 到 的 簡 單 特 徵 包 含 有 : 頭 髮 顏 色 身 高 體 重 是 否 有 塗 抹 防 曬 乳 液, 與 最 後 是 否 有 曬 傷 的 結 果 於 是 你 想 從 所 觀 察 到 的 8 個 樣 本 (samples) 中, 嘗 試 得 到 曬 傷 的 原 因 [Winston992] 表 5- 曬 傷 研 究 觀 察 紀 錄 名 字 髮 色 身 高 體 重 乳 液 曬 傷 Sarah 金 色 普 通 輕 無 是 Dana 金 色 高 普 通 有 否 Alex 棕 色 矮 普 通 有 否 Annie 金 色 矮 普 通 無 是 Emily 紅 色 普 通 重 無 是 Pete 棕 色 高 重 無 否 John 棕 色 普 通 重 無 否 Katie 金 色 矮 輕 有 否 在 符 號 式 學 習 中, 建 構 一 個 最 小 的 識 別 樹 (identification tree) 用 以 區 分 曬 傷 與 否, 是 一 個 簡 單 的 方 法, 並 且 可 以 歸 納 出 曬 傷 的 規 則 識 別 樹 為 一 樹 狀 結 構, 6

17 其 節 點 (node) 為 特 徵, 其 分 支 (branch) 的 標 籤 為 特 徵 值, 最 後 樹 的 終 端 節 點 (terminal node, 即 沒 有 分 支 的 節 點 ) 應 只 包 含 同 一 類 的 樣 本 要 建 構 一 個 最 小 的 識 別 樹, 需 要 借 用 資 訊 理 論 (information theory) 中 的 熵 (entropy) 的 概 念, 其 定 義 如 下 : c n n bc b log 2 n n bc b 其 中,n b 是 在 分 支 b 的 樣 本 數,n bc 是 在 分 支 b 中 類 別 為 c 的 樣 本 數 熵 的 定 義 可 用 為 測 量 物 件 的 亂 度 (disorder) 假 設 目 前 分 支 b 只 有 兩 個 類 別 A 和 B, 它 們 的 樣 本 數 都 一 樣, 則 其 亂 度 值 為, 是 亂 度 的 最 大 值, 其 計 算 如 下 : c n n bc b nbc log = log 2 + log 2 = + n = b 相 反 的, 假 設 目 前 分 支 b 只 剩 下 一 個 類 別, 只 剩 下 A 類 或 是 只 剩 下 B 類, 那 其 亂 度 值 為 0, 是 亂 度 的 最 小 值, 其 計 算 如 下 : c n n bc b nbc log = 2 2 n ( log ) + ( 0 log 0) = ( 0) + ( 0) 0 2 = b 如 圖 5-4 所 示, 當 從 兩 個 類 別 樣 本 數 相 同 逐 漸 移 至 只 剩 下 一 個 類 別 時, 其 亂 度 值 慢 慢 地 由 變 成 0 其 中, 類 別 分 數 為 某 類 別 的 樣 本 數 除 以 所 有 樣 本 總 數, 如 上 式 中 的 n n bc b 亂 度 類 別 分 數 類 別 分 數 亂 度 值 0/8 0 /8, 7/ /8, 6/ /8, 5/ /8 圖 5-4 兩 個 類 別 不 同 比 例 相 混 的 亂 度 分 佈 情 形 7

18 得 到 每 一 個 分 支 的 亂 度 值 後, 可 以 進 一 步 計 算 由 一 個 節 點 其 所 生 出 所 有 分 支 的 平 均 亂 度, 其 公 式 如 下 : b n b n t d b 其 中,d b 為 分 支 b 的 亂 度,n t 為 所 有 分 支 的 樣 本 數 總 和,n b 如 前 所 定 義 為 分 支 b 的 樣 本 數 在 建 構 一 個 最 小 的 識 別 樹 時, 我 們 分 別 以 不 同 的 特 徵 為 節 點, 計 算 其 節 點 的 平 均 亂 度 值, 最 小 的 平 均 亂 度 值 代 表 分 類 結 果 較 為 一 致, 因 此 應 可 得 較 小 的 識 別 樹 我 們 再 繼 續 求 取 下 一 層 的 最 小 平 均 亂 度 值, 一 直 到 節 點 中 只 包 含 一 個 類 別 ( 其 亂 度 值 為 0) 為 止 髮 色 0.50 身 高 0.69 Sarah Dana Annie Kaite 金 色 紅 色 Emily 棕 色 Alex Pete John Alex Annie Kaite 矮 普 通 Sarah Emily John 高 Dana Pete 體 重 0.94 乳 液 0.6 Sarah Kaite 輕 普 通 Dana Alex Annie 重 Emily Pete John Sarah Annie Emily Pete John 無 有 Dana Alex Kaite 圖 5-5 全 部 8 個 樣 本 以 不 同 特 徵 分 類 結 果 以 表 5- 的 8 個 樣 本 為 例, 分 別 以 不 同 特 徵 為 節 點, 其 分 支 如 圖 5-5 所 示, 其 中 打 勾 者 ( ) 為 曬 傷, 其 餘 則 沒 有 曬 傷 先 計 算 頭 髮 顏 色 這 一 特 徵 的 平 均 亂 度 值, 金 髮 有 4 人, 其 中 有 2 人 曬 傷, 另 外 2 人 沒 有, 紅 髮 只 有 人 且 曬 傷, 棕 髮 有 3 人 均 沒 有 曬 傷 其 計 算 如 下 : 8

19 b nb db n t = log2 + log = 繼 續 計 算 其 它 特 徵 的 平 均 亂 度 值, 並 標 示 於 圖 5-5 不 同 特 徵 節 點 的 右 方 因 為 髮 色 的 平 均 亂 度 值 最 低, 所 以 被 選 為 建 構 識 別 樹 的 第 一 個 特 徵 由 圖 5-5 中 得 知, 頭 髮 為 紅 色 和 棕 色 的 人 只 有 一 種 類 別, 金 髮 的 人 則 有 兩 種 類 別,2 人 曬 傷,2 人 則 無 因 此 我 們 繼 續 針 對 金 髮 4 人 計 算 其 它 特 徵 的 平 均 亂 度, 如 圖 5-6 所 示, 其 計 算 結 果 標 示 於 節 點 右 方 從 以 上 結 果 可 知, 是 否 塗 抹 防 曬 乳 液 可 得 最 佳 結 果, 因 此 被 選 為 第 二 個 測 試 的 特 徵, 因 其 平 均 亂 度 值 為 0, 代 表 其 所 有 分 支 都 只 剩 下 一 個 類 別, 因 此 我 們 可 以 建 構 出 一 個 最 小 的 識 別 樹 如 圖 5-7(a) 所 示 Annie Kaite 矮 身 高 普 通 Sarah 0.5 高 Dana Sarah Kaite 輕 體 重 普 通 Dana Annie.0 乳 液 0.0 重 Sarah Annie 無 有 Dana Kaite 圖 5-6 金 髮 的 4 個 樣 本 再 以 其 它 三 種 特 徵 分 類 的 結 果 我 們 可 以 再 進 一 步 從 所 建 構 的 識 別 樹 中 得 出 曬 傷 的 規 則 ( 原 因 ) 來, 我 們 從 髮 色 節 點 沿 著 分 支 往 下 走, 直 到 遇 見 終 端 點 為 止, 因 此 我 們 可 以 得 到 四 條 規 則, 如 圖 5-7(b) 所 示 根 據 上 面 所 得 到 的 四 條 規 則, 我 們 可 以 從 其 中 兩 項 特 徵, 猜 測 其 他 人 有 沒 有 可 能 會 曬 傷 9

20 髮 色 金 色 紅 色 棕 色 無 乳 液 有 Emily Alex Pete John Sarah Annie Dana Kaite (a) 識 別 樹 S: If 頭 髮 是 金 色 有 使 用 防 曬 乳 液 Then 沒 有 曬 傷 S3: If 頭 髮 是 紅 色 Then 有 曬 傷 S2: If 頭 髮 是 金 色 沒 有 使 用 防 曬 乳 液 Then 有 曬 傷 (b) 識 別 規 則 S4: If 頭 髮 是 棕 色 Then 沒 有 曬 傷 圖 5-7 曬 傷 檢 驗 識 別 樹 與 其 所 得 規 則 5-6 類 神 經 網 路 學 習 是 要 透 過 我 們 的 頭 腦, 因 而 研 究 大 腦 神 經 細 胞 的 運 作, 可 以 幫 助 我 們 了 解 學 習 在 腦 神 經 是 如 何 完 成 的, 進 而 可 以 模 擬 神 經 細 胞 的 運 作 以 達 到 類 似 學 習 的 功 能 據 估 計 人 腦 約 有 一 千 億 (0 ) 個 神 經 細 胞, 每 個 神 經 細 胞 約 有 一 千 (0 3 ) 根 連 結 與 其 他 神 經 細 胞 相 連, 因 此 人 腦 中 約 有 一 百 萬 億 (0 4 ) 根 連 結, 形 成 一 個 高 度 連 結 網 狀 的 神 經 網 路 (neural network) 科 學 家 們 相 信 : 人 腦 的 資 訊 處 理 工 作 即 是 透 過 這 些 連 結 來 完 成 的 [ 葉 怡 成 993] 神 經 細 胞 的 形 狀 與 一 般 的 細 胞 有 很 大 的 不 同, 它 包 括 : 細 胞 體 (soma): 神 經 細 胞 中 呈 核 狀 的 處 理 機 構 ; 軸 突 (axon): 神 經 細 胞 中 呈 軸 索 狀 的 輸 送 機 構 ; 樹 狀 20

21 突 (dendrites): 神 經 細 胞 中 呈 樹 枝 狀 的 輸 出 入 機 構 ; 與 突 觸 (synapse): 樹 狀 突 上 呈 點 狀 的 連 結 機 構 根 據 神 經 學 家 的 研 究 發 現 : 當 神 經 細 胞 透 過 神 經 突 觸 與 樹 狀 突 從 其 它 神 經 元 輸 入 脈 波 訊 號 後, 經 過 細 胞 體 處 理, 產 生 一 個 新 的 脈 波 訊 號 如 果 脈 波 訊 號 夠 強, 將 產 生 一 個 約 千 分 之 一 秒 00 毫 伏 的 脈 波 訊 號 這 個 訊 號 再 經 過 軸 突 傳 送 到 它 的 神 經 突 觸, 成 為 其 它 神 經 細 胞 的 輸 入 脈 波 訊 號 如 果 脈 波 訊 號 是 經 過 興 奮 神 經 突 觸 (excitatory synapse), 則 會 增 加 脈 波 訊 號 的 速 率 ; 相 反 的, 如 果 脈 波 訊 號 是 經 過 抑 制 神 經 突 觸 (inhibitory synapse), 則 會 減 少 脈 波 訊 號 的 速 率 因 此, 脈 波 訊 號 的 速 率 是 同 時 取 決 於 輸 入 脈 波 訊 號 的 速 率, 以 及 神 經 突 觸 的 強 度 而 神 經 突 觸 的 強 度 可 視 為 神 經 網 路 儲 存 資 訊 之 所 在, 神 經 網 路 的 學 習 即 在 調 整 神 經 突 觸 的 強 度 2 : i W j W 2j W ij θ j net j f Y j : : n W nj neuron j 圖 5-8 人 工 神 經 細 胞 結 構 類 神 經 網 路 (artificial neural networks), 或 譯 為 人 工 神 經 網 路, 則 是 指 模 仿 生 物 神 經 網 路 的 資 訊 處 理 系 統, 它 是 由 許 多 人 工 神 經 細 胞 ( 又 稱 為 類 神 經 元 人 工 神 經 元 與 處 理 單 元 ) 所 組 成, 人 工 神 經 細 胞, 如 圖 5-8 所 示 本 節 將 探 討 最 古 老 也 是 最 基 本 的 類 神 經 網 路 模 式 感 知 機 (perceptron), 它 是 957 年 由 Rosenblatt 所 提 出 感 知 機 的 基 本 原 理 是 由 腦 神 經 模 型 所 啟 發, 特 別 是 943 年 McCulloch 和 Pitts 所 共 同 提 出 的 數 學 模 型, 通 稱 為 MP 模 型, 以 及 Hebb 所 提 出 的 神 經 元 學 習 規 則, 通 稱 為 Hebb 學 習 規 則 2

22 MP 模 型 的 要 點 如 下 :() 神 經 元 的 狀 態 為 興 奮 或 抑 制 二 者 之 一, 可 用 0 表 示 抑 制 狀 態, 用 表 示 興 奮 狀 態 (2) 神 經 元 與 其 它 神 經 元 間 的 連 結, 可 用 一 個 加 權 值 (weight) 表 示 連 結 強 度 (3) 神 經 元 的 狀 態 會 經 由 連 結 輸 出 到 其 它 神 經 元, 成 為 其 輸 入 (4) 神 經 元 的 狀 態 受 其 相 連 的 神 經 元 制 約, 當 從 這 些 神 經 元 傳 來 的 輸 入 訊 號 ( 即 該 神 經 元 的 狀 態 ) 經 過 連 結 以 加 權 乘 積 和 計 算 所 得 的 值 大 於 某 門 檻 值 (threshold) 時, 神 經 元 的 狀 態 將 成 為 興 奮 狀 態 ; 否 則, 為 抑 制 狀 態 以 公 式 表 示 為 : Y = f net ) (5-6.) j ( j net = W θ (5-6.2) j i ij i j 其 中,W ij 為 神 經 元 i 與 神 經 元 j 間 的 連 結 強 度, 即 連 結 加 權 值, i 為 從 神 經 元 i 傳 來 的 輸 入 訊 號,θ j 為 神 經 元 j 的 門 檻 值,f 為 轉 換 函 數 (transfer function), 通 常 為 一 個 階 梯 函 數 (step function), 其 定 義 如 下 : if S > 0 f ( S) = (5-6.3) 0 if S 0 (5) 神 經 網 路 的 學 習 過 程 即 在 調 整 神 經 元 間 的 連 結 強 度, 即 連 結 加 權 值 而 Hebb 學 習 規 則 的 要 點 如 下 : 調 整 兩 個 神 經 元 間 連 結 加 權 值 的 原 則 為 當 第 i 個 與 第 j 個 神 經 元 同 時 處 於 興 奮 狀 態 時, 則 其 連 結 應 當 加 強 Hebb 學 習 規 則 與 動 物 行 為 科 學 中 的 條 件 反 射 學 說 一 致 感 知 機 的 網 路 架 構 有 兩 種, 如 圖 5-9 所 示, 一 含 有 隱 藏 層, 另 一 種 則 無 它 們 皆 包 括 有 輸 入 層 與 輸 出 層 輸 入 層 用 以 表 現 網 路 的 輸 入 變 數, 其 處 理 單 元 數 目 依 問 題 而 定, 使 用 線 性 轉 換 函 數 f ( ) =, 亦 即 輸 入 值 即 為 輸 出 值 隱 藏 層 用 以 表 現 輸 入 處 理 單 元 間 的 交 互 影 響, 其 處 理 單 元 數 目 通 常 以 實 驗 方 式 決 定 其 最 佳 數 目, 隱 藏 層 可 以 有 一 層 以 上, 也 可 以 沒 有 輸 出 層 用 以 表 現 網 路 的 輸 出 變 數, 22

23 其 處 理 單 元 的 數 目 依 問 題 而 定 輸 入 變 數 形 成 一 個 輸 入 向 量, 輸 出 變 數 形 成 一 個 輸 出 向 量 輸 出 向 量 輸 出 層 輸 出 向 量 隱 藏 層 輸 入 向 量 輸 入 層 輸 入 向 量 圖 5-9 感 知 機 網 路 架 構 我 們 以 簡 單 的 無 隱 藏 層 的 感 知 機 來 說 明 類 神 經 網 路 的 學 習 機 制 在 神 經 網 路 的 學 習 中, 樣 本 資 料 以 數 值 形 式 表 示, 每 一 個 樣 本 都 包 含 有 輸 入 向 量 = [, 2,, n ] 和 目 標 輸 出 向 量 T = [T, T 2,, T m ] 一 般 將 所 有 的 樣 本 資 料 隨 機 分 為 兩 部 分, 一 部 分 為 訓 練 樣 本 (training samples), 另 一 部 分 為 測 試 樣 本 (test samples) 首 先, 將 感 知 機 初 始 化, 即 給 定 每 一 個 連 結 一 個 隨 機 亂 數 值 然 後 將 一 個 訓 練 樣 本 的 輸 入 向 量 輸 入 感 知 機 中, 並 利 用 公 式 (5-6.) 和 (5-6.2) 計 算 其 推 論 輸 出 向 量 Y = [Y, Y 2,, Y m ] 此 網 路 利 用 由 訓 練 樣 本 輸 入 之 目 標 輸 出 向 量 T 和 透 過 網 路 推 得 的 推 論 輸 出 向 量 Y 相 較 之 下 的 誤 差, 作 為 修 正 連 結 中 的 加 權 值 的 依 據, 以 從 訓 練 樣 本 中 學 習 隱 含 的 輸 入 向 量 與 輸 出 向 量 之 對 應 關 係 差 距 量 δ j 計 算 公 式 如 下 : δ = T Y (5-6.4) j j j 若 δ j > 0, 表 示 推 論 輸 出 變 數 Y j 小 於 目 標 輸 出 變 數 T j, 根 據 公 式 (5-6.2) 得 知 23

24 連 結 加 權 值 W ij 太 小, 故 應 增 加 W ij 的 值 相 反 的, 若 δ j < 0, 表 示 推 論 輸 出 變 數 Y j 大 於 目 標 輸 出 變 數 T j, 根 據 公 式 (5-6.2) 得 知 連 結 加 權 值 W ij 太 大, 故 應 減 少 W ij 的 值 加 權 值 之 改 變 量 公 式 可 表 達 如 下 : W ij = η δ (5-6.5) j i 其 中,η 為 學 習 速 率 (learning rate), 控 制 每 次 加 權 值 改 變 量 的 幅 度 公 式 (5-6.5) 中, 加 權 值 之 改 變 量 也 應 與 輸 入 訊 號 i 成 正 比, 因 為 訊 號 越 大, 其 修 正 量 也 應 越 大 同 理, 輸 出 單 元 的 門 檻 值 改 變 量 公 式 計 算 如 下 : θ = η (5-6.6) j δ j 類 神 經 網 路 的 學 習 過 程, 通 常 以 一 次 一 個 訓 練 樣 本 的 方 式 進 行, 直 到 學 習 完 所 有 的 訓 練 樣 本 為 止, 稱 為 一 個 學 習 循 環 (learning cycle) 加 權 值 與 門 檻 值 的 修 正 可 採 用 逐 步 學 習 (step learning) 或 批 次 學 習 (batch learning), 逐 步 學 習 是 每 輸 入 一 個 訓 練 樣 本, 計 算 其 加 權 值 與 門 檻 值 的 修 正 量 後 立 即 修 改 而 批 次 學 習 是 在 一 個 學 習 循 環 後, 計 算 所 有 訓 練 樣 本 的 加 權 值 與 門 檻 值 的 修 正 量 後, 依 下 列 公 式 計 算 其 整 體 修 正 量 而 修 改 之 m Wij m Wij = (5-6.7) N m θ j m θ j = (5-6.8) N 其 中,m 表 示 第 m 個 樣 本, 而 N 為 訓 練 樣 本 總 數 一 個 網 路 可 以 將 訓 練 樣 本 反 覆 學 習 多 個 循 環, 直 到 滿 足 終 止 條 件 為 止 而 終 止 條 件 可 訂 為 執 行 一 定 數 目 的 學 習 循 環 或 是 網 路 已 收 斂 ( 即 誤 差 不 再 有 明 顯 變 化 ) 感 知 機 的 誤 差 程 度 可 用 總 錯 誤 率 E 定 義 如 下 : 24

25 N E E = (5-6.9) N 其 中,N E 為 誤 分 類 樣 本 總 數, 而 誤 分 類 樣 本 是 指 測 試 樣 本 中, 其 推 論 輸 出 值 最 大 的 輸 出 單 元, 與 目 標 輸 出 值 最 大 的 輸 出 單 元 不 是 同 一 個 單 元 之 樣 本 感 知 機 網 路 演 算 法 整 理 於 圖 5-20, 其 中 粗 體 字 ( 如 W θ T 與 δ 等 ) 表 示 整 個 矩 陣 或 是 向 量 學 習 過 程 :. 設 定 網 路 參 數 2. 以 均 佈 隨 機 亂 數 設 定 加 權 值 矩 陣 W, 與 偏 權 值 向 量 θ 初 始 值 3. 輸 入 一 個 訓 練 樣 本 的 輸 入 向 量 與 目 標 輸 出 向 量 T 4. 計 算 推 論 輸 出 向 量 Y 5. 計 算 差 距 量 δ 6. 計 算 加 權 值 矩 陣 修 正 量 W, 以 及 偏 權 值 向 量 修 正 量 θ 7. 更 新 加 權 值 矩 陣 W, 以 及 偏 權 值 向 量 θ 8. 重 複 步 驟 3 至 步 驟 7 直 至 到 收 斂 或 執 行 一 定 數 目 的 學 習 循 環 回 想 過 程 :. 設 定 網 路 參 數 2. 讀 入 加 權 值 矩 陣 W 與 偏 權 值 向 量 θ 3. 輸 入 一 個 測 試 樣 本 的 輸 入 向 量 4. 計 算 推 論 輸 出 向 量 Y 圖 5-20 感 知 機 的 學 習 過 程 與 回 想 過 程 以 下 我 們 以 表 5-2 的 4 個 訓 練 樣 本 說 明 感 知 機 的 學 習 過 程 樣 本 的 輸 入 向 量 包 含 有 兩 個 輸 入 變 數 和 2, 輸 出 向 量 T 只 包 含 一 個 輸 出 變 數 T, 因 此 我 們 可 以 設 計 一 個 簡 單 不 含 隱 藏 層 的 感 知 機 網 路 架 構 如 圖 5-2 所 示, 包 含 兩 個 輸 入 單 元 與 一 個 輸 出 單 元, 編 號 標 示 於 其 旁 令 初 始 加 權 值 W 3 =.0,W 23 =.0, 輸 出 單 元 的 門 檻 值 θ 3 = 0.0 假 設 網 路 採 批 次 學 習, 其 學 習 速 率 η = 0.5 在 此 範 例 中, 因 為 只 有 一 個 輸 出, 為 簡 便 起 見, 我 們 將 其 下 標 省 略, 如 用 θ 代 表 θ 3,Y 25

26 代 表 Y 3 等 表 5-2 訓 練 樣 本 樣 本 (m) 2 T Y #3 輸 出 層 W 3 W 23 # #2 輸 入 層 2 圖 5-2 感 知 機 網 路 架 構 第 一 個 樣 本 =, 2 =,T = 0 的 學 習 過 程 如 下 : 首 先 計 算 推 論 輸 出 值 Y, 由 公 式 (5-6.2) 得 net = W + W θ = (.0)( ) + (.0)( ) = 由 公 式 (5-6.) 與 (5-6.3) 得 知 Y = f ( net) = f (0.0) = 0 接 下 來, 計 算 輸 出 層 差 距 量 δ, 由 公 式 (5-6.4) 得 δ = T Y = 0 0 = 0 26

27 最 後, 計 算 加 權 值 修 正 量 W 3 和 W 23 及 偏 權 值 修 正 量 θ, 由 公 式 (5-6.5) 和 (5-6.6) 得 W W = η δ = (0.5)(0)( ) 0, 3 = = η δ = (0.5)(0)( ) 0, 23 2 = θ = η δ = (0.5)(0) = 0 其 它 三 個 樣 本 的 學 習 過 程 如 表 5-3 所 示 表 5-3 感 知 機 的 訓 練 樣 本 學 習 過 程 m 2 T net Y δ m W 3 m W 23 m θ 根 據 公 式 (5-6.7) 和 (5-6.8) 計 算 批 次 學 習 的 加 權 值 與 門 檻 值 如 下 : W W 4 m W3 m= 3 = = N (0.0) + ( 0.5) + (0.0) + (0.5) 0.0 = = m W23 m= 23 = = 4 N (0.0) + (0.5) + (0.0) + (0.5).0 = = , 0.5, m θ m= (0.0) + ( 0.5) + (0.0) + ( 0.5).0 θ = = = = 0.5 N 4 2 於 是, 我 們 更 新 網 路 的 連 結 加 權 值 與 門 檻 值 如 下 : W 3 = W3 + W3 = (.0) + (0.0) =.0 W 23 = W23 + W23 = (.0) + (0.5) = 0.5 θ = θ + θ = ( 0.0) + ( 0.5) =

28 繼 續 以 上 步 驟, 直 到 網 路 收 斂 為 止 我 們 可 以 稍 微 研 究 一 下, 在 上 個 範 例 中, 兩 個 輸 入 變 數 和 2 可 以 表 示 成 二 維 平 面 中 的 水 平 與 垂 直 軸, 於 是 四 個 樣 本 可 以 表 示 成 落 在 平 面 上 四 個 點, 其 中 第 一 個 樣 本 其 輸 出 為 0, 我 們 用 黑 點 表 示, 其 它 三 個 樣 本 輸 出 為, 我 們 以 白 點 表 示, 因 此 樣 本 有 黑 白 兩 個 類 別 在 計 算 網 路 輸 出 Y 時, net = W + W θ = 剛 好 是 一 條 直 線, 代 表 一 條 邊 界 線 將 平 面 分 割 為 兩 部 分 因 此 網 路 的 學 習 即 在 自 動 找 到 一 條 邊 界 線 能 將 黑 白 兩 類 樣 本 點 分 開 此 條 邊 界 線 初 始 設 定 為 2 = 0, 為 一 對 角 線, 並 沒 有 將 黑 點 與 白 點 分 開, 如 圖 5-22 所 示 經 過 第 一 個 批 次 學 習 後, 此 直 線 往 逆 時 針 方 向 修 正 成 2 2 = 此 網 路 在 經 過 幾 個 批 次 學 習 後 會 收 斂, 此 時 邊 界 線 會 將 黑 點 與 白 點 分 開 2 修 正 後 邊 界 線 原 先 邊 界 線 2 2 = 2 = 0 圖 5-22 經 過 第 一 次 批 次 學 習 後 的 邊 界 線 修 正 的 結 果 5-7 基 因 演 算 法 基 因 演 算 法 (genetic algorithms), 或 稱 為 遺 傳 演 算 法, 是 由 John Holland 於 28

29 970 年 代 所 提 出 的, 他 利 用 電 腦 來 模 擬 達 爾 文 (Charles Darwin) 的 天 演 論 物 競 天 擇, 適 者 生 存 的 概 念, 用 以 解 決 最 佳 化 (optimization) 問 題, 以 求 得 較 佳 解 在 生 物 的 染 色 體 (chromosomes) 中 含 有 為 數 眾 多 的 基 因 (genes), 每 個 基 因 具 有 某 些 特 性 生 物 在 繁 殖 下 一 代 時, 由 父 母 的 染 色 體, 經 過 交 換 (crossover) 突 變 (mutation) 與 複 製 (reproduction) 而 產 生 新 的 染 色 體, 因 此 具 有 父 母 各 一 部 份 的 基 因, 所 以 遺 傳 有 父 母 的 部 分 特 質 在 基 因 演 算 法 中,Holland 簡 單 以 0 與 表 示 基 因, 而 染 色 體 用 以 表 示 問 題 可 能 的 答 案 因 此, 將 問 題 的 答 案 表 達 成 0 與 的 字 串, 稱 為 編 碼 (encoding) 如 圖 5-23(a) 所 示 為 兩 個 4 位 元 字 串 的 染 色 體 在 基 因 演 算 法 中, 我 們 簡 單 以 一 個 染 色 體 代 表 一 個 個 體 (individual), 而 一 個 群 體 (population) 是 由 N 個 個 體 所 構 成, 也 形 成 一 個 世 代 (generation) 在 目 前 這 個 世 代 的 群 體 中, 有 些 個 體 比 較 優 秀, 依 據 優 生 學 理 論, 優 秀 的 個 體 繁 衍 的 下 一 代 變 得 更 優 秀 的 機 率 比 較 高 因 而 在 一 代 一 代 的 演 進 下, 染 色 體 會 越 來 越 優 秀 在 基 因 演 算 法 中, 我 們 訂 定 一 個 適 應 函 數 (fitness function), 以 評 估 每 一 個 個 體 的 適 應 情 形 適 應 程 度 越 高 的 個 體 代 表 越 優 秀, 被 選 擇 來 繁 衍 下 一 代 的 機 率 也 比 較 高 (a) 0 0 (b) 0 0 (c) 0 (d) 圖 5-23 一 對 染 色 體 的 交 換 運 算 在 進 行 交 換 的 運 算 時, 必 須 選 擇 一 對 染 色 體, 決 定 交 換 點 (crossover point), 將 兩 個 染 色 體 在 交 換 點 的 位 置 切 成 兩 段, 然 後 將 後 段 互 相 對 調, 即 構 成 一 對 新 的 染 色 體 以 上 例 的 一 對 染 色 體 說 明, 假 設 交 換 點 位 置 為 2, 意 即 在 第 二 個 基 因 與 29

30 第 三 個 基 因 之 間 為 交 換 點 所 在 位 置, 如 圖 5-23(b) 所 示 於 是 先 切 成 四 段 如 圖 5-23(c) 所 示 然 後, 後 段 部 分 互 相 交 換, 可 得 到 一 對 新 的 染 色 體, 其 結 果 如 圖 5-23(d) 所 示 至 於 突 變 運 算, 即 將 基 因 值 改 變, 意 即 若 原 先 基 因 為 0, 突 變 後 為, 反 之 亦 然 完 整 的 基 因 演 算 法 列 於 圖 首 先 將 問 題 的 可 能 答 案 編 碼 成 固 定 長 度 的 染 色 體, 然 後 選 定 群 體 中 染 色 體 的 數 目 N, 交 換 機 率 p c, 突 變 機 率 p m 2. 定 義 適 應 函 數 f 3. 隨 機 產 生 初 始 群 體 中 的 N 個 染 色 體 :x, x 2,, x N 4. 計 算 每 一 個 染 色 體 的 適 應 函 數 值 :f(x ), f(x 2 ),, f(x N ) 5. 從 目 前 的 群 體 中 選 出 一 對 染 色 體, 以 為 配 對 之 用 染 色 體 的 選 擇 與 其 適 應 函 數 值 有 關 適 應 程 度 越 高 的 染 色 體 被 選 擇 的 機 率 就 越 高 6. 利 用 基 因 運 算 子 交 換 突 變 和 複 製, 以 產 生 一 對 新 的 染 色 體 7. 將 新 產 生 的 染 色 體 放 入 新 的 群 體 中 8. 重 複 步 驟 5, 直 到 新 產 生 的 染 色 體 數 目 達 到 N 為 止 9. 將 新 的 群 體 取 代 舊 的 群 體 0. 跳 到 步 驟 4, 重 複 整 個 行 程, 直 到 終 止 條 件 滿 足 為 止 圖 5-24 基 因 演 算 法 讓 我 們 舉 例 說 明 基 因 演 算 法 是 如 何 運 作 的 假 設 尋 找 函 數 (5x x 2 ) 的 最 大 值 ( 當 x = 7.5 時, 函 數 值 為 是 最 大 值 ), 其 中 參 數 x 介 於 0 到 5 之 間 為 簡 化 起 見, 令 x 為 整 數, 以 二 進 位 表 示 需 要 四 個 位 元, 因 此 染 色 體 可 以 由 四 個 基 因 所 組 成, 如 表 5-4 所 示 表 5-4 染 色 體 的 基 因 表 示 法 整 數 二 進 位 碼 整 數 二 進 位 碼 整 數 二 進 位 碼

31 假 設 群 體 的 染 色 體 數 N 為 6, 交 換 機 率 p c 為 0.7, 突 變 機 率 p m 為 0.00 在 本 例 中, 適 應 函 數 定 義 為 f(x) = (5x x 2 ) 基 因 演 算 法 於 是 開 始 隨 機 產 生 初 始 群 體 的 6 個 染 色 體, 並 計 算 其 適 應 函 數 值, 如 表 5-5 所 示 表 5-5 初 始 隨 機 所 產 生 的 群 體 染 色 體 標 籤 染 色 體 字 串 整 數 值 適 應 值 適 應 比 例 % % % % % % 染 色 體 的 選 擇 一 般 採 用 輪 盤 方 式 選 擇 (roulette wheel selection), 如 圖 5-25 所 示 每 一 染 色 體 在 輪 盤 所 佔 的 面 積 與 其 適 應 函 數 值 成 正 比, 亦 即 其 適 應 比 例 (= 適 應 值 / 適 應 值 總 和 ) 因 此, 有 較 高 的 適 應 值, 其 在 輪 盤 中 所 佔 面 積 會 比 較 大, 相 對 的, 被 選 擇 的 機 會 也 會 比 較 大 在 圖 5-25 中, 染 色 體 的 適 應 比 例 為 6.5%, 其 所 佔 輪 盤 面 積 從 0% 到 6.5%, 染 色 體 2 的 適 應 比 例 為 20.2%, 其 所 佔 輪 盤 面 積 從 6.5% 到 36.7% ( = 6.5% %), 其 餘 類 推 我 們 使 用 隨 機 亂 數, 其 值 落 於 某 個 染 色 體 的 範 圍 內, 就 選 取 該 染 色 體 00.0% 6 6.5% 75.2% % 4 43.% 49.5% 圖 5-25 輪 盤 方 式 選 擇 3

32 第 i 個 世 代 交 換 (Crossover) i 2 i f = 36 f = 44 6 i i 3 i 4 i 5 i 6 i f = 4 f = 4 f = 56 f = 54 i 2 i i 5 i 第 i+ 個 世 代 突 變 (Mutation) i f = 56 6 i i+ 0 0 f = 50 2 i i+ 0 f = 44 i 0 i 4 i f = 44 5 i i+ 0 0 f = 54 2 i i 6 i+ 0 f = 56 5 i 0 圖 5-26 基 因 演 算 法 的 週 期 假 設 染 色 體 6 與 2 首 先 被 選 取, 交 換 點 隨 機 定 為 2, 並 且 產 生 一 隨 機 亂 數 值 大 於 交 換 機 率 p c, 所 以 此 兩 個 染 色 體 會 進 行 交 換, 產 生 兩 個 新 的 染 色 體 6 與 2, 如 圖 5-26 所 示 另 一 對 染 色 體 與 5 於 交 換 點 為 的 地 方 也 進 行 交 換, 最 後 選 取 的 染 色 體 2 與 5 因 所 產 生 的 隨 機 亂 數 值 小 於 交 換 機 率, 故 而 沒 有 交 32

33 換, 直 接 複 製 成 新 的 染 色 體 2 與 5 在 突 變 運 算 中, 針 對 每 個 新 染 色 體 中 的 每 個 基 因, 隨 機 產 生 一 數 值, 若 其 值 小 於 突 變 機 率 p m, 則 將 該 基 因 改 變 ; 若 原 為, 則 改 為 0, 若 原 為 0, 則 改 為 在 此 例 中, 有 的 第 二 個 基 因 與 2 的 第 三 個 基 因 產 生 突 變, 因 而 產 生 兩 個 突 變 的 新 染 色 體 與 2 至 此 所 產 生 的 6 個 新 染 色 體 成 為 下 一 個 世 代 的 群 體, 形 成 一 個 基 因 演 算 法 的 週 期 如 是 繼 續 下 一 個 週 期, 直 到 滿 足 終 止 條 件 為 止 而 終 止 條 件 一 般 設 定 為 經 過 M 個 世 代 的 演 進, 或 是 最 佳 適 應 值 已 收 斂 ( 上 一 世 代 與 下 一 世 代 的 最 佳 適 應 值 的 差 距 小 於 某 個 預 定 值 ) 從 上 例 中 可 以 看 到, 新 一 代 的 染 色 體, 其 適 應 值 普 遍 提 高, 其 平 均 值 為 50.67, 比 前 一 代 的 平 均 適 應 值 高 出 結 語 在 本 章 中, 我 們 介 紹 了 人 工 智 慧 領 域 中, 一 些 傳 統 研 究 的 基 本 原 理, 包 含 : 困 難 問 題 的 解 決 電 腦 遊 戲 專 家 系 統 自 然 語 言 處 理 機 械 學 習 類 神 經 網 路 與 基 因 演 算 法 等 介 紹 完 其 基 本 原 理 後, 並 輔 以 有 趣 的 範 例, 詳 細 說 明 其 運 作 的 過 程, 使 讀 者 能 更 深 入 了 解 人 工 智 慧 是 如 何 利 用 基 本 原 理, 並 透 過 電 腦 演 算 法 來 解 決 複 雜 與 困 難 的 問 題 本 章 所 介 紹 的 部 分, 在 整 個 人 工 智 慧 領 域 中, 只 是 冰 山 的 一 角 人 工 智 慧 的 研 究 乃 在 利 用 電 腦 來 模 擬 人 的 智 慧, 故 而 有 關 人 類 智 慧 的 探 討 人 類 智 慧 的 運 作 與 設 計 智 慧 型 系 統 的 研 究, 均 包 含 在 人 工 智 慧 的 領 域 中 因 此 與 人 工 智 慧 相 關 的 研 究 領 域 甚 廣, 除 資 訊 科 學 外, 尚 包 含 : 心 理 學 語 言 學 神 經 學 邏 輯 學 哲 學 認 知 科 學 生 物 學 等 等 在 現 代 的 電 腦 中, 處 處 可 以 看 到 人 工 智 慧 的 應 用, 讓 電 腦 更 有 智 慧, 例 如 智 慧 型 大 樓 內 的 種 種 設 備 希 望 透 過 本 章 的 介 紹, 能 引 發 讀 者 對 人 工 智 慧 的 興 趣, 進 一 步 將 人 工 智 慧 的 研 究 應 用 於 利 益 人 類 社 會 33

34 5-9 參 考 文 獻 [DeepBlue2005] Deep Blue URL 存 取 日 期 2005/03/2. [Giarratano2004] Joseph Giarratano and Gary Riley, Expert Systems: Principles and Programming, Fourth Edition, [Hopcroft979] John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 979. [Negnevitsky2002] Michael Negnevitsky, Artificial Intelligence: A Guide to Intelligent Systems, Addison Wesley, [Nilsson998] Nils J. Nilsson, Artificial Intelligence: A New Synthesis, Morgan Kaufmann, 998. [Rich99] E. Rich and K. Knight, Artificial Intelligence, Second Edition, McGraw-Hill, 99. [Weizenbaum966] Joseph Weizenbaum, ELIZA A Computer Program For the Study of Natural Language Communication Between Man and Machine, Communications of the ACM, Volume 9, Number (January 966): [Winston 992] Patrick H. Winston, Artificial Intelligence, Third Edition, Addison-Wesley, 992. [ 孫 家 麟 985] 孫 家 麟, 微 電 腦 的 人 工 智 慧 實 驗, 松 崗 電 腦 圖 書 資 料 有 限 公 司,985 年 [ 葉 怡 成 993] 葉 怡 成, 類 神 經 網 路 模 式 應 用 與 實 作, 儒 林 圖 書 有 限 公 司,993 年 8 月 二 版 34

35 5-0 習 作. 有 三 個 傳 教 士 與 三 個 野 蠻 人 要 渡 河, 岸 邊 剛 好 有 一 艘 能 乘 載 兩 人 的 竹 筏 任 何 時 候, 在 河 岸 兩 邊 如 果 傳 教 士 的 人 數 比 野 蠻 人 少, 就 會 被 野 蠻 人 吃 掉 請 問 : 要 如 何 才 能 將 此 六 人 安 全 地 渡 河 到 對 岸 去? 2. 假 設 在 井 字 遊 戲 中, 目 前 的 盤 局 如 下 MA 下 一 步 要 如 何 走 才 可 以 得 到 最 大 的 勝 算? 請 畫 出 如 圖 5-4 的 樹 狀 結 構 圖 來 分 析, 以 得 出 最 好 的 答 案 3. 假 設 機 器 人 羅 碧 看 到 一 隻 動 物, 猜 想 牠 是 企 鵝 若 羅 碧 利 用 後 向 鍊 結 法 推 論, 那 它 必 須 要 辨 識 到 哪 些 特 徵 才 能 確 定 是 企 鵝? 4. 請 畫 出 英 文 句 子 I want the fast printer 的 剖 析 樹 5. 在 機 械 學 習 的 範 例 中, 假 設 Dana 的 體 重 改 為 重, 且 會 曬 傷 請 建 構 出 一 識 別 樹, 並 得 出 其 識 別 規 則 6. 在 感 知 機 的 範 例 中, 經 過 幾 個 學 習 循 環 會 收 斂? 請 畫 出 每 一 次 學 習 後 修 正 的 邊 界 線, 了 解 邊 界 線 修 正 的 過 程 7. 在 基 因 演 算 法 的 範 例 中, 假 設 選 取 交 換 與 突 變 的 方 式 都 與 圖 5-26 產 生 第 i + 個 世 代 一 樣, 求 得 第 i + 2 個 世 代 的 6 個 新 染 色 體 5- 索 引 二 劃 人 工 智 慧 artificial intelligence 四 劃 井 字 遊 戲 Tic-Tac-Toe 文 法 grammar 五 劃 由 上 而 下 剖 析 top-down parsing 由 下 而 上 剖 析 bottom-up parsing 加 權 值 weight 世 代 generation 35

36 六 劃 自 然 語 言 natural languages 交 換 crossover 交 換 點 crossover point 七 劃 抑 制 神 經 突 觸 inhibitory synapse 八 劃 知 識 庫 knowledge base 知 識 表 達 法 knowledge representation 狀 態 轉 變 圖 state transition diagram 事 實 facts 門 檻 值 threshold 九 劃 前 提 antecedents 前 向 鍊 結 forward chaining 後 向 鍊 結 backward chaining 突 觸 synapse 突 變 mutation 染 色 體 chromosomes 十 劃 特 徵 features 剖 析 樹 parse tree 訓 練 樣 本 training samples 個 體 individual 十 一 劃 規 則 rules 專 家 系 統 expert systems 專 家 知 識 expertise 推 論 機 制 inference engine 符 號 式 學 習 symbolic learning 連 接 式 學 習 connectionist learning 細 胞 體 soma 基 因 genes 基 因 演 算 法 genetic algorithms 十 二 劃 極 大 極 小 法 minimaxing method 評 估 函 數 evaluation function 結 論 consequents 軸 突 axon 測 試 樣 本 test samples 最 佳 化 optimization 階 梯 函 數 step function 十 三 劃 電 腦 遊 戲 computer game 電 腦 程 式 語 言 computer programming languages 感 知 機 perceptron 36

37 群 體 population 複 製 reproduction 十 四 劃 語 彙 分 析 lexical analysis 語 法 分 析 syntactical analysis 語 意 分 析 semantic analysis 十 五 劃 熵 entropy 輪 盤 方 式 選 擇 roulette wheel selection 適 應 函 數 fitness function 編 碼 encoding 十 六 劃 機 械 學 習 machine learning 樹 狀 突 dendrites 興 奮 神 經 突 觸 excitatory synapse 遺 傳 演 算 法 genetic algorithm 學 習 循 環 learning cycle 十 八 劃 轉 換 函 數 transfer function 十 九 劃 識 別 樹 identification tree 類 神 經 網 路 artificial neural networks 5-2 致 謝 衷 心 感 謝 陳 俊 文 彭 建 文 和 陳 志 遠 等 三 位 博 士 生 的 細 心 校 稿, 讓 錯 誤 降 到 最 低 ; 尤 其 感 謝 陳 俊 文 所 提 出 的 諸 多 建 議, 使 得 本 章 內 容 更 為 充 實 可 讀 性 更 為 提 升, 在 此 致 上 十 二 萬 分 的 謝 意 最 後 要 感 謝 系 主 任 王 英 宏 教 授 給 我 這 個 機 會, 將 自 己 心 中 長 久 以 來 的 心 願 : 以 簡 明 易 懂 的 文 字 介 紹 人 工 智 慧 的 基 本 原 理 給 初 學 者 得 以 如 願 以 償, 並 感 謝 主 任 在 這 段 期 間 耐 心 等 待 本 章 的 完 稿 洪 文 斌 敬 上 中 華 民 國 九 十 四 年 四 月 十 三 日 於 淡 江 大 學 資 訊 工 程 學 系 37