第 二 讲 语 言 知 识 的 形 式 化 表 示 http://ccl.pku.edu.cn/doubtfire/
提 纲 1 自 然 语 言 现 象 举 例 2 关 于 自 然 语 言 的 知 识 3 知 识 的 表 示 3.1 有 限 状 态 自 动 机 ( 正 则 表 达 式 ) 3.2 上 下 文 无 关 文 法 3.3 特 征 结 构 与 合 一 运 算 4 小 结 2
1 自 然 语 言 现 象 举 例 例 1 A. It is unlikely that Lee will be elected. A. Lee is unlikely to be elected. B. It is improbable that Lee will be elected. B. * Lee is improbable to be elected. Ivan A.Sag & Thomas Wasow, 1999, Syntactic Theory: A Formal Introduction, CSLI Publications 3
自 然 语 言 现 象 举 例 ( 续 ) 例 2a C. 张 三 爱 好 下 围 棋 C. 下 围 棋 是 张 三 的 爱 好 D. 张 三 喜 欢 下 围 棋 D. * 下 围 棋 是 张 三 的 喜 欢 4
自 然 语 言 现 象 举 例 ( 续 ) 例 2b C. 读 过 那 本 书 的 学 生 不 多 C. 那 本 书 读 过 的 学 生 不 多 D. 参 观 故 宫 的 学 生 回 来 了 D. * 故 宫 参 观 的 学 生 回 来 了 5
自 然 语 言 现 象 举 例 ( 续 ) 例 3 E. 这 件 事 容 易 办 E. 办 这 件 事 容 易 F. 这 件 事 好 办 F. 办 这 件 事 好 6
自 然 语 言 现 象 举 例 ( 续 ) 例 4 G. 马 文 才 害 死 了 梁 山 伯 H. 梁 山 伯 被 马 文 才 害 死 了 G / * H I., 欺 骗 了 祝 英 台 7
自 然 语 言 现 象 举 例 ( 续 ) 例 5 J. 桌 子 上 有 两 本 书 K. 有 两 本 书 在 桌 子 上 J? K L., 一 盏 台 灯, 一 个 笔 筒, 还 有 一 摞 练 习 本 8
2 关 于 自 然 语 言 的 知 识 对 于 自 然 语 言, 人 具 有 以 下 三 个 层 面 的 能 力 : 人 们 一 般 可 以 判 断 一 个 表 达 形 式 是 否 属 于 一 种 语 言, 比 如 上 面 例 1 和 例 2 中, 人 们 能 够 判 断 出 句 子 A' 不 属 于 英 语 ( 即 不 被 说 英 语 者 接 受 ), 句 子 C' 不 属 于 汉 语 ( 即 不 被 说 汉 语 者 接 受 ); 对 于 一 种 语 言 中 的 两 个 表 达 形 式, 人 们 一 般 可 以 判 断 二 者 之 间 是 否 具 有 某 种 关 系, 比 如 同 义 关 系, 两 个 表 达 式 所 对 应 的 命 题 之 间 的 逻 辑 蕴 含 关 系, 等 等 像 上 面 例 3, 人 们 能 够 判 断 句 子 E 跟 E 是 同 义 关 系, 但 F 跟 F 不 是 同 义 关 系 对 于 一 种 语 言 中 两 个 同 义 的 表 达 式, 人 们 一 般 可 以 判 断 在 特 定 场 合 下 使 用 哪 一 个 表 达 式 更 好, 比 如 上 面 例 4 和 例 5 9
语 言 知 识 的 分 层 句 法 知 识 语 义 知 识 语 篇 知 识 语 音 知 识 ( 参 见 附 录 ) 10
语 言 知 识 (1) X 的 Y 结 构 形 式 :dzjg (2) X= 名 词 形 容 词 动 词 ; Y= 名 词 (3) 爱 好 => 动 词 名 词 喜 欢 => 动 词 张 三 => 名 词 11
语 言 知 识 ( 续 ) (1) 好 1, 好 2, 容 易 => 形 容 词 (2)A + B : zzjg (A= 形 容 词,B= 动 词 ) (3)B + A : zwjg (4)zzjg(a,b) zwjg(b,a) (5) 好 1 只 能 进 入 zzjg (= easy ) 好 2 只 能 进 入 zwjg(= good ) 容 易 可 以 进 入 zzjg, zwjg? a A; b B 12
对 语 言 知 识 的 认 识 代 数 学 ( 理 性 主 义 ) 的 定 义 方 法 确 定 性 定 义 方 法 语 言 是 由 规 则 所 定 义 的 句 子 的 集 合 统 计 学 ( 经 验 主 义 ) 的 定 义 方 法 不 确 定 性 定 义 方 法 语 言 就 是 一 个 概 率 分 布, 又 称 为 语 言 模 型 语 言 中 的 每 一 个 句 子 都 有 自 己 的 出 现 概 率 13
3 知 识 的 表 示 用 自 然 语 言 来 描 述 关 于 自 然 语 言 的 知 识 用 形 式 语 言 来 描 述 关 于 自 然 语 言 的 知 识 对 象 语 言 (Object Language) 元 语 言 (Meta Language) 14
从 自 然 语 言 到 形 式 语 言 避 免 混 淆, 动 词 不 是 动 词 避 免 罗 嗦, 从 前 有 个 山, 山 上 有 个 庙 可 计 算, 结 构 化 的 数 据 15
形 式 语 言 (Formal Language) 的 一 些 例 子 2+5 = 7 2H 2 + O 2 = 2H 2 O P & Q (P: 董 永 是 放 牛 郎 ;Q: 董 永 喜 欢 七 仙 女 ) IS_COWBOY (x) & IS_Vega(y) & LOVE (x, y) 16
计 算 机 语 言 # include "stdio.h" main ( ) { printf("\n\t hello, world"); return 0; } 一 个 C 语 言 例 子 17
如 何 描 述 ( 严 格 定 义 ) 一 个 语 言 枚 举 给 出 语 言 中 的 所 有 句 子 对 于 含 无 限 多 个 句 子 的 语 言 不 合 适 文 法 给 出 生 成 语 言 中 所 有 句 子 的 方 法 当 且 仅 当 能 够 用 该 方 法 产 生 的 句 子 才 属 于 该 语 言 自 动 机 列 举 性 定 义 描 述 性 定 义 给 出 识 别 该 语 言 中 句 子 的 机 械 方 法 过 程 性 定 义 18
3.1 有 限 状 态 自 动 机 N q 0 N q 1 V q 2 N ε 有 限 状 态 自 动 机 (Finite State Automata) 19
状 态 转 移 表 (state transition table) 弧 ( 输 入 ) N V ε 状 态 转 移 q 0 q 1 q 1 q 1 q 2 q 2 q 2 q 1 20
状 态 转 移 过 程 示 例 字 符 串 状 态 转 移 过 程 N V q 0 q 1 q 2 N V N q q 0 1 q 2 q 2 N V N V N q q 0 1 q 2 q 2 q 1 q 2 2 21
有 限 状 态 自 动 机 (FSA) 的 形 式 定 义 一 个 有 限 状 态 自 动 机 M 是 一 个 五 元 组 : (Q, Σ, q 0, F, δ) 有 限 个 状 态 组 成 的 状 态 集 : Q 有 限 字 母 组 成 的 字 母 表 : Σ 开 始 状 态 q 0 Q 终 止 状 态 的 集 合 F Q 状 态 转 移 函 数 δ(q,i): Q xσ Q 22
识 别 一 个 十 进 制 实 数 的 自 动 机 + 0~9 0~9-0~9 q 0 q 1 q 2. q 3 0~9 23
正 则 表 达 式 (Regular Expression) + 0~9 0~9-0~9 q 0 q 1 q 2. q 3 0~9 (\+ -)? [0-9]+(\.[0-9]*)? Jurafsky & Martin(2000), 第 2 章 24
Eliza 中 的 正 则 表 达 式 操 作 人 : My boyfriend made me come here. Eliza: Your Boyfriend made you come here. 人 : He says I m depressed much of time. Eliza: I am sorry to hear you are depressed. 正 则 表 达 式 替 换 : 1) /(.*) my (.*)/ => / \1 your \2 / 2) / (.*) I m (.*)/ => / \1 you are \2/ 3) /.* you are (depressed sad).*/ => / I am sorry to hear you are \1 / Eliza 的 操 作 就 是 做 一 连 串 的 正 则 表 达 式 的 匹 配 和 替 换 Jurafsky & Martin(2000), 第 2 章,pp32-33. 25
弧 上 带 输 出 的 FSTN:Transducer 有 限 状 态 转 录 机 N : n N : n N : n V : v q 0 q 1 q 2 董 永 喜 欢 七 仙 女 - Dong_Yong loves Qi_Xiannv 董 永 七 仙 女 喜 欢 - Dong_Yong Qi_Xiannv loves 26
课 堂 练 习 构 造 一 个 有 限 状 态 转 移 网 络, 可 以 接 受 汉 语 的 重 叠 形 式 AABB,ABB,ABAB, 27
课 堂 练 习 构 造 识 别 名 词 词 组 的 FSA 三 本 书 语 法 书 阿 Q 的 书 阿 Q 的 三 本 书 阿 Q 的 三 本 语 法 书 阿 Q 的 三 本 汉 语 语 法 书 阿 Q 的 三 本 古 代 汉 语 语 法 书 阿 Q 和 他 的 三 本 汉 语 语 法 书 28
从 FSA 到 上 下 文 无 关 文 法 (CFG) FSA: 无 法 描 述 自 然 语 言 的 层 次 结 构 特 性 听 说 服 装 设 计 很 吃 香 听 说 那 套 服 装 设 计 得 很 有 品 位 听 说 孩 子 丢 了 听 说 孩 子 丢 了 一 只 鞋 听 说 北 京 队 大 败 听 说 北 京 队 大 败 上 海 队 29
3.2 上 下 文 无 关 文 法 符 号 字 母 表 : 有 限 个 任 意 符 号 组 成 的 非 空 集 合 Σ 例 1: 所 有 汉 字 组 成 的 集 合 构 成 一 个 字 母 表 例 2: 汉 语 中 所 有 的 词 也 构 成 一 个 字 母 表 例 3: 字 母 a, b, c 也 组 成 一 个 字 母 表 字 符 串 : 由 字 母 表 Σ 上 的 字 符 组 成 的 长 度 有 限 的 序 列 若 字 母 表 Σ= {a, b}, 则 a, b, ab, aba, aabb 等 等 都 是 字 母 表 上 的 字 符 串 30
语 言 的 形 式 定 义 语 言 : 是 字 母 表 上 的 字 符 串 的 任 意 集 合 例 1. 若 Σ= {a, b}, 则 定 义 在 Σ 上 的 语 言 可 以 是 L1={ab, ba} L2={ab, abab, ababab, } 31
形 式 文 法 形 式 文 法 : 一 个 形 式 文 法 G 由 四 个 部 分 组 成, 可 记 作 G={V N, V T, S, P }, 其 中 : V N : 称 为 文 法 G 的 非 终 结 符 号 字 母 表,V N 不 出 现 在 G 所 表 示 的 语 言 集 合 的 句 子 中 ; V T : 称 为 文 法 G 的 终 结 符 号 字 母 表,G 所 表 示 的 语 言 的 句 子 由 V T 中 的 元 素 组 成, V N V T = φ ; S : 代 表 句 子 符 号,S V N P : 代 表 一 组 式 子 组 成 的 集 合,P 中 的 式 子 具 有 如 下 形 式 : α β 32
形 式 文 法 ( 续 ) 产 生 式 规 则 (production rule) α β 重 写 规 则 (rewriting rule) 产 生 式 需 要 满 足 下 面 的 条 件 : 1)α 可 以 是 V N 和 V T 上 的 任 意 字 符 串, 不 能 是 空 字 符 ; 2)β 可 以 是 V N 和 V T 上 的 任 意 字 符 串, 可 以 是 空 字 符 ; 3)P 中 至 少 有 一 个 产 生 式 中 的 α 得 由 S 来 充 当 ; 33
上 下 文 无 关 文 法 对 产 生 式 规 则 α β 做 如 下 约 定 : α = 1 α VN β ( VN UVT * ) 这 样 的 形 式 文 法 就 是 上 下 文 无 关 文 法 34
一 个 上 下 文 无 关 文 法 的 例 子 设 文 法 G 0 = (V N, V T, S, P ), 其 中 V N = {S, NP, VP, N, V }, V T = { 喜 欢, 知 道, 董 永, 七 仙 女 }, P 中 产 生 式 如 下 : 1. S -> NP VP 2. VP -> VP NP 3. VP -> VP S 4. VP -> V 5. NP -> N 6. N -> 董 永 7. N -> 七 仙 女 8. V -> 喜 欢 9. V -> 知 道 35
直 接 推 导 推 导 句 型 句 子 语 言 直 接 推 导 : S => NP VP 推 导 :S=> NP VP => NP V => N V 上 式 可 以 简 写 为 :S * N V 句 型 :NP VP, NP V, N V, 是 G 0 的 句 型 句 子 : 仅 含 终 结 符 号 的 句 型,N V 语 言 : 给 定 一 个 文 法 G 0, 该 文 法 所 产 生 的 所 有 句 子 组 成 的 集 合, 称 为 该 文 法 所 定 义 的 语 言 36
G 0 所 描 述 的 语 言 L 0 S1: 董 永 喜 欢 七 仙 女 S2: 董 永 知 道 董 永 喜 欢 七 仙 女 S3: 七 仙 女 知 道 董 永 S4: 七 仙 女 喜 欢 董 永 知 道 董 永 S5: 七 仙 女 喜 欢 董 永 董 永 董 永 七 仙 女 37
不 属 于 L 0 的 字 符 串 S1 : 知 道 喜 欢 知 道 七 仙 女 S2 : 董 永 董 永 七 仙 女 知 道 喜 欢 S3 : 七 仙 女 董 永 喜 欢 38
13 句 子 结 构 的 树 形 描 述 S NP VP 1 2 句 法 结 构 分 析 树 11 VP S 9 NP 3 VP 4 VP 7 NP 5 14 12 N V N V 10 8 N 6 董 永 知 道 董 永 喜 欢 七 仙 女 39
文 法 的 三 个 作 用 生 成 ; 产 生 语 言 L 中 所 有 的 句 子 ; 判 定 : 一 个 字 符 串 (String) 是 否 属 于 语 言 L; 分 析 : 得 到 L 中 句 子 的 结 构 树 ; 分 析 出 句 子 的 结 构 是 进 行 自 然 语 言 信 息 处 理 的 基 础 比 如 移 位 变 换, 就 必 须 建 立 在 结 构 分 析 的 基 础 上 张 三 知 道 李 四 不 会 当 逃 兵 -> 当 逃 兵, 张 三 知 道 李 四 不 会 -> * 知 道 李 四, 张 三 不 会 当 逃 兵 40
句 法 结 构 分 析 的 效 用 : 控 制 转 换 s s np vp vp s vp s np vp dp vp vp vp vp np n v n d v v n vp np np vp vp s np vp dp vp v n n v n d v 张 三 知 道 李 四 不 会 当 逃 兵 当 逃 兵 张 三 知 道 李 四 不 会 41
练 习 对 于 语 言 L={ab, aabb, aaabbb,, a n b n, } n 是 自 然 数 (1) 请 写 出 L 的 上 下 文 无 关 文 法 ; (2) 要 求 产 生 式 右 部 不 能 超 过 两 个 符 号 ; 42
乔 姆 斯 基 范 式 ( Chomsky Normal Form) A B C A A a B C D 1 A B C D 引 入 一 个 新 的 非 终 结 符 X A 一 个 三 分 支 规 则 可 以 转 换 为 两 个 二 分 支 规 则 1 2 A B X X C D B X C D 43
练 习 1 写 出 汉 语 表 示 自 然 数 的 词 的 CFG 2 用 你 写 的 CFG, 画 出 下 列 数 字 的 分 析 树 : 一 亿 零 三 百 万 三 万 六 千 五 百 八 十 一 44
基 于 简 单 范 畴 的 文 法 的 缺 陷 范 畴 划 分 有 不 同 的 颗 粒 度 (granularity) 例 如 英 语 句 子 的 构 成 规 则 : S NP VP 如 果 考 虑 到 英 语 主 谓 语 单 复 数 的 搭 配, 就 要 将 NP 和 VP 分 成 NPsingular 和 NPplural 和 VPsingular 和 VPplural, 并 其 将 规 则 改 写 成 : S NPsingular VPsingular S NPplural VPplural 范 畴 划 分 有 不 同 的 角 度 (perspective) np_count np np np_uncount np_animate np_inanimate 45
3.3 特 征 结 构 与 合 一 运 算 引 入 特 征 结 构 弥 补 简 单 范 畴 的 不 足 特 征 结 构 (Feature Structure) 复 杂 特 征 集 (Complex Feature Set) 特 征 结 构 定 义 为 特 征 的 集 合 所 谓 特 征, 是 一 个 由 属 性 和 值 组 成 的 二 元 组, 属 性 也 称 为 特 征 名, 值 也 称 为 特 征 值 在 特 征 结 构 中, 要 求 所 有 的 特 征 的 属 性 互 不 相 同 空 特 征 结 构 : 不 含 任 何 特 征 的 特 征 结 构 attribute 1 =value 1 attribute 2 =value 2 attribute n =value n 记 作 :[ ] 46
特 征 结 构 的 嵌 套 与 共 享 1) 特 征 值 可 以 是 一 个 字 符 串 值 或 数 值 等 简 单 类 型, 也 可 以 是 另 一 个 特 征 结 构, 这 就 是 所 谓 的 特 征 结 构 的 嵌 套 ; 为 了 区 别 于 特 征 结 构 形 式 的 特 征 值, 我 们 把 简 单 的 字 符 串 形 式 的 特 征 值 称 为 原 子 (atom) 2 ) 两 个 特 征 可 以 共 享 一 个 值, 这 是 所 谓 的 特 征 值 的 共 享 ( 也 称 为 重 入 / Reentrance ) 47
48 特 征 结 构 示 例 ( 框 式 表 示 法 ) 2 : : : : 音 节 重 叠 是 词 性 动 词 词 语 听 听 单 数 数 名 词 词 性 七 仙 女 词 语 宾 语 动 词 词 性 喜 欢 词 语 述 语 谓 语 单 数 数 名 词 词 性 董 永 词 语 主 语 : : : : : : : : : : : : 词 性 名 词 词 语 七 仙 女 受 事 词 性 名 词 词 语 董 永 施 事 论 元 词 性 动 词 词 语 喜 欢 谓 词 : : : : : : : : : : a. 简 单 特 征 结 构 b. 复 杂 特 征 结 构 ( 嵌 套 ) c. 复 杂 特 征 结 构
特 征 结 构 的 表 表 示 法 (( 主 语 : ( 词 语 : 董 永 )( 词 性 : 名 词 )( 数 : 单 数 )) ( 谓 语 : ( 述 语 :( 词 语 : 喜 欢 )( 词 性 : 动 词 )) ( 宾 语 :( 词 语 : 七 仙 女 )( 词 性 : 名 词 )( 数 : 单 数 )))) 49
有 向 无 环 图 (Directed Acyclic Graph) 特 征 结 构 的 图 表 示 法 主 语 词 性 数 词 形 名 词 董 永 单 数 边 (edge) 表 示 特 征 节 点 (node) 表 示 特 征 值 谓 语 述 语 名 词 宾 语 词 性 数 词 形 七 仙 女 单 数 50
两 个 特 征 结 构 的 值 共 享 例 子 : He is a student. 在 特 征 结 构 表 示 中, 一 般 用 数 字 表 示 重 入 的 特 征 结 构 在 重 入 的 多 个 特 征 结 构 中, 只 需 在 一 处 说 明 其 特 征 值 cat:v lex:be per:3 1 num:singular 2 sub: obj: cat:r lex:he per:1 num:2 cat:n lex:student num:3 det: cat:art lex:a num:singular 3 51
两 个 特 征 结 构 的 值 共 享 ( 续 ) Type SEM = VP = Type SEM = VP = CONJ Type SEM = VP = 1 1 1 七 仙 女 知 道 而 且 理 解 董 永 的 选 择 知 道 与 理 解 形 成 联 合 结 构, 这 两 个 动 词 的 语 义 特 征 共 享 相 同 的 值, 并 且 整 个 联 合 结 构 的 语 义 特 征 也 取 相 同 的 值 52
两 个 特 征 结 构 的 值 共 享 ( 续 ) 同 意 和 答 应 的 区 别 cat:v lex: 同 意 arg 1 : cat:n cat:n arg 2 : 1 cat:v lex: 答 应 arg 1 : cat:n 1 arg 2 : cat:n arg 3 : cat:v arg x :1 arg 3 : cat:v arg x :1 53
特 征 结 构 的 共 享 ( 有 向 图 表 示 ) 我 我 arg 1 arg 1 arg x 同 意 arg 3 明 天 去 答 应 arg 3 明 天 去 arg 2 arg x arg 2 你 你 我 同 意 你 明 天 去 vs. 我 答 应 你 明 天 去 54
特 征 结 构 间 的 包 孕 关 系 subsumption 特 征 结 构 F1 包 孕 F2, 记 作 F1 & F2, 当 且 仅 当 (1) 若 特 征 f F1, 则 f F2, 并 且 (2) 若 f 的 值 是 特 征 结 构, 则 valuef1( f ) & valuef 2( f ) (3) 若 f 的 值 是 简 单 原 子, 则 valuef 1( f ) = valuef 2( f ) 空 特 征 结 构 包 孕 任 何 特 征 结 构 55
特 征 结 构 包 孕 关 系 举 例 Number SG PERSON 3 [ Number SG] & [ Agree [ Number SG ] Number SG [] & PERSON 3 & CAT Agree NP Number SG PERSON 3 [ Number SG] /& [ Number PL] 56
特 征 结 构 的 合 一 运 算 合 一 运 算 (Unification): 将 两 个 独 立 的 特 征 结 构 F1,F2 组 合 为 一 个 新 的 特 征 结 构 F3, 满 足 条 件 : F1 & F3 并 且 F2 & F3 合 一 的 含 义 是 : 对 两 个 特 征 结 构 进 行 类 似 于 集 合 求 并 的 一 种 运 算, 从 而 可 以 在 小 的 特 征 结 构 基 础 上 形 成 大 的 特 征 结 构, 这 种 运 算 非 常 适 于 刻 划 小 的 语 言 单 位 发 展 为 大 的 语 言 单 位 的 过 程 中 的 信 息 增 加, 即 F3 中 包 含 了 F1,F2 所 包 含 的 信 息 ( 合 一 运 算 的 单 调 性 monotonic) 57
合 一 成 功 失 败 合 一 结 果 为 空 合 一 操 作 有 成 功 或 失 败 两 种 可 能 : 合 一 成 功, 则 原 来 的 两 个 独 立 的 特 征 结 构 成 为 同 一 个 特 征 结 构 ; 合 一 失 败, 维 持 原 状 注 意 : 合 一 失 败 和 合 一 结 果 为 空 是 不 同 的 合 一 失 败, 两 个 特 征 结 构 之 间 不 发 生 共 享 ; 合 一 结 果 为 空, 表 示 合 一 成 功, 两 个 特 征 结 构 共 享, 变 成 同 一 个 特 征 结 构, 只 是 这 个 特 征 结 构 是 空 特 征 结 构 ; 只 有 两 个 空 特 征 结 构 合 一, 结 果 才 是 空 58
合 一 实 例 ( 一 ) 结 构 : 述 宾 A = 功 能 : 述 语 B = 词 性 : 动 词 及 物 : 是 词 语 : 咳 嗽 词 性 : 动 词 及 物 : 否 A B = U φ 合 一 失 败 59
合 一 实 例 ( 二 ) 施 事 : C 谓 词 : 知 道 : [ 语 义 类 : 人 ] 语 义 类 : 人 令 A = B= 词 语 董 永, 其 中 C = 则 将 C 和 B 合 一 后, 特 征 结 构 A 变 为 : 语 义 类 : 人 施 事 : 词 语 : 董 永 谓 词 : 知 道 合 一 成 功 60
合 一 实 例 ( 三 ) E = F = Agree: Number: Singular 1 Subject: Agree:1 Subject: Agree:Person: 3 E F = Number: Singular Agree: 1 Person: 3 Subject: Agree:1 合 一 成 功 61
合 一 运 算 的 性 质 交 换 律 :A B=B A 结 合 律 :A (B C)=(A B) C 合 一 运 算 的 执 行 顺 序 与 结 果 无 关 (order independent) 合 一 运 算 的 结 合 律 使 得 特 征 结 构 真 正 成 为 一 种 描 述 性 知 识 表 示 方 法, 而 不 是 过 程 性 的 表 示 方 法 描 述 性 知 识 表 示 方 法 的 含 义 在 于, 对 于 一 个 变 量 的 约 束 和 赋 值 是 等 同 的, 我 们 可 以 在 对 一 个 变 量 赋 值 之 前 就 给 出 对 它 的 约 束, 而 不 必 等 到 对 这 个 变 量 赋 值 之 后 才 对 它 进 行 约 束 比 如, 我 们 可 以 在 词 典 中 指 出, 汉 语 动 词 同 意 的 arg 3 的 arg 1 必 须 和 同 意 的 arg 2 合 一, 虽 然 这 时 我 们 并 不 知 道 在 具 体 的 句 子 中 同 意 的 各 个 arg 是 什 么 特 征 结 构 的 描 述 性 特 点 有 利 于 在 词 典 中 给 出 词 语 的 个 性 化 描 述 62
合 一 运 算 的 两 个 基 本 作 用 (1) 检 查 两 个 特 征 结 构 所 包 含 的 信 息 是 否 相 容, 这 可 以 作 为 语 言 成 分 组 合 时 的 测 试 手 段 ( 比 如 前 面 例 一 ) (2) 当 两 个 相 容 的 特 征 结 构 组 合 成 更 大 的 特 征 结 构 时, 信 息 增 加 ( 比 如 上 页 例 二 三 ) 63
合 一 对 于 语 言 知 识 表 示 和 处 理 的 意 义 由 于 句 法 和 语 义 分 析 都 可 以 用 合 一 来 作 为 基 本 运 算, 不 仅 句 子 的 合 法 性 可 以 通 过 语 义 手 段 来 判 断, 而 且, 还 可 以 把 句 子 的 句 法 结 构 和 语 义 表 示 用 合 一 运 算 这 种 方 式 更 加 自 然 的 衔 接 起 来 对 不 同 的 复 杂 特 征 集 进 行 合 一 运 算, 其 结 果 同 运 算 所 进 行 的 先 后 次 序 无 关, 不 论 合 一 从 那 个 方 向 开 始, 也 不 论 是 先 合 一 还 是 后 合 一, 合 一 的 结 果 都 是 相 同 的 合 一 运 算 的 这 种 无 序 性 非 常 便 于 并 行 处 理, 而 且 还 使 我 们 有 可 能 自 由 地 选 择 分 析 算 法 和 自 然 语 言 描 述 的 语 法 理 论 64
小 结 有 限 状 态 自 动 机 上 下 文 无 关 文 法 特 征 结 构 ( 合 一 运 算 ) 线 性 序 列 (Linear Structure) 树 结 构 (Tree Structure) 图 结 构 (Graph Structure) 形 式 表 示 方 法 仅 仅 是 工 具, 它 本 身 并 不 增 加 知 识, 只 是 让 知 识 以 严 密 清 晰 的 方 式 呈 现 出 来 以 形 式 化 的 方 式 来 表 述 自 然 语 言 知 识 一 方 面 便 于 计 算, 另 一 方 面 也 有 助 于 发 现 语 言 学 问 题 65
进 一 步 阅 读 文 献 冯 志 伟 等 译 (2005) 自 然 语 言 处 理 综 论 第 1 章, 第 10.3.2, 第 13 章 杜 淑 敏 等 (1990) 编 译 程 序 设 计 原 理, 北 京 大 学 出 版 社 何 成 武 (1990) 自 动 机 理 论 及 其 应 用, 科 学 出 版 社 王 兵 山 吴 兵 编 (1988) 形 式 语 言, 国 防 科 技 大 学 出 版 社 Noam Chomsky (1959) On certain formal properties of grammars, Information and Control, 1959, 1, pages 91-112 陆 汝 钤 (2000) 人 工 智 能 ( 上 册 ), 科 学 出 版 社 陆 汝 钤 (1993) 数 学 计 算 逻 辑, 湖 南 教 育 出 版 社 沙 新 时 等 (1993) 基 于 合 一 语 法 的 通 用 句 法 分 析 器 : 设 计 与 实 施, 载 中 文 信 息 学 报 1993 年 第 2 期 66
附 录 1 Chomsky Hierarchy G 0 : 无 限 制 重 写 文 法 G 1 : 上 下 文 相 关 文 法 G 2 : 上 下 文 无 关 文 法 0 1 2 3 G 3 : 正 则 文 法 L 0 : 递 归 可 枚 举 语 言 L 1 : 上 下 文 相 关 语 言 L 2 : 上 下 文 无 关 语 言 L 3 : 正 则 语 言 67
PSG, CSG, CFG, RG PSG: 无 限 制 CSG: CFG: RG: α α α = = 1 β 1 α VN α V N or β = β = β tn Nt ( VN UVT T * ) t V, N V N 68
附 录 2 文 法 自 动 机 和 语 言 语 法 自 动 机 语 言 复 杂 度 0 型 无 限 制 短 语 结 构 文 法 图 灵 机 递 归 可 枚 举 语 言 半 可 判 定 1 型 上 下 文 有 关 文 法 线 性 有 界 自 动 机 上 下 文 有 关 语 言 NP 完 全 2 型 上 下 文 无 关 文 法 下 推 自 动 机 上 下 文 无 关 语 言 多 项 式 3 型 正 则 文 法 有 限 自 动 机 正 则 语 言 线 性 69
各 型 文 法 的 判 定 难 度 PSG: 半 可 判 定 对 于 一 个 属 于 G type0 的 句 子 L, 总 可 以 在 确 定 步 内 判 断 出 是 ; 但 对 于 一 个 不 属 于 G type0 的 句 子 L, 不 存 在 一 个 算 法, 可 以 在 确 定 步 内 判 断 出 否 CSG: 可 判 定, 复 杂 度 :NP 完 全 CFG: 可 判 定, 复 杂 度 : 多 项 式 RG: 可 判 定, 复 杂 度 : 线 性 参 阅 : 陆 汝 钤 (1993) 数 学 计 算 逻 辑, 湖 南 教 育 出 版 社 第 六 八 章 70
有 关 形 式 文 法 的 问 题 文 法 的 二 义 性 (Ambiguity) 各 型 文 法 的 描 述 能 力 不 同 文 法 之 间 的 等 价 性 ( 强 等 价 弱 等 价 ) 文 法 的 机 器 学 习 问 题 对 于 CFG, 不 存 在 一 个 确 定 的 算 法, 可 以 在 给 定 句 子 集 合 L 基 础 上, 学 到 L 的 CFG 文 法 ( 这 个 数 学 结 果 是 对 Chomsky 关 于 儿 童 语 言 能 力 先 天 说 的 一 个 支 持 ) 71
有 关 自 动 机 的 问 题 自 动 机 的 分 类 各 类 自 动 机 的 形 式 定 义 各 类 自 动 机 与 各 型 形 式 文 法 的 对 应 关 系 72
附 录 3 递 归 转 移 网 络 (Recursive Transition Network) 1. S -> NP VP 2. VP -> VP NP 3. VP -> VP S 4. VP -> V 5. NP -> N NP VP S q 0 q 1 q 2 VP q 0 VP NP q 1 q 2 S V N NP q 0 q 1 ATN(Augmented Transition Network): 增 加 了 条 件 测 试 与 寄 存 器 的 RTN 73
附 录 4 跟 语 音 相 关 的 语 言 知 识 (1) 单 音 节 双 音 节 单 音 节 暗 喜 * 暗 暗 喜 双 音 节 * 暗 高 兴 ( 喜 欢 ) 暗 暗 高 兴 ( 喜 欢 ) 连 一 连 单 音 节 连 查 了 五 家 公 司 一 连 查 了 五 家 公 司 双 音 节 * 连 调 查 了 五 家 公 司 一 连 调 查 了 五 家 公 司 74
附 录 4 跟 语 音 相 关 的 语 言 知 识 (2) 轻 音 重 音 例 子 张 三 一 天 就 挣 三 十 块 钱, 大 家 都 很 羡 慕 他 张 三 一 天 就 挣 三 十 块 钱, 大 家 都 很 同 情 他 意 义 就 前 量 少 就 后 量 少 轻 音 重 音 他 刚 结 婚, 又 正 在 度 蜜 月, 怎 么 就 遭 遇 了 这 样 的 不 幸 呢? 张 三 又 来 了 例 子 意 义 追 加 重 复 75