知识创新随机过程最大熵模型

摘要

根据创新知识的形成受已有相关知识影响的假设，综合运用概率统计、最优化、最大熵原理构建了知识创新随机过程最大熵模型，给出了以已有知识x∈X为约束的新知识y∈Y的条件概率p(y|x)。模型具有随机性与因果性对立统一的特点。

正文

《1 引言》

1 引言

知识创新的核心问题之一是如何表达已有知识, 以及如何应用已有知识进行分析、推理, 从而得到新知识, 其中尤以不确定性知识的推理和表达最为重要, 也十分困难。国内外学者利用数学方法进行的理论与实践研究重点集中在知识创新规律探索和知识获取技术两个方面, 其中知识获取的主要方法有:粗糙集、遗传算法、神经网络^{[1,2,3,4,5,6,7,8]}, 知识创新规律探索尚处起步阶段, 方法相对分散且不成熟, 有拟线性微分方程、SPA (set pair analysis) 等^[9,10]。这些模型共同的问题是对非结构化且大范围知识对象的处理有局限性, 路径依赖性较强。本文的基本假设是:新知识的形成受已有相关知识的影响, 即新知识不能孤立出现。以此为基础构建的知识创新随机过程最大熵模型试图反映、记录并利用知识创新中存在的规律, 模型具有随机性与因果性对立统一的特点, 是解决知识创新问题的一种尝试。

《2 问题的数学表达[11]》

2 问题的数学表达[11]

设知识创新随机过程P, 输出的创新知识为有限集Y, ∀y∈Y的生成受相关已有知识的影响或约束, 定义与Y有关的已有相关知识集为X, 在给定∀x∈X条件下, 随机过程建模的目的是求出形成新知识y∈Y的条件概率 P (y|x) , 即对P (y|x) 进行估计。用P表示所有条件概率分布集合即P (y|x) ∈P。

模型的输入是从经过处理的知识库中抽取的样本集T,

$Τ = {(x_{1}, y_{1}) ‚ \dots ‚ (x_{i}, y_{i}) ‚ \dots ‚ (x_{Ν}, y_{Ν})}$ $Τ = {(x_{1}, y_{1}) ‚ \dots ‚ (x_{i}, y_{i}) ‚ \dots ‚ (x_{Ν}, y_{Ν})}$

∀x_i∈X, ∀y_i∈Y, 1≤i≤N, (x, y) 的经验分布为

$\tilde{Ρ} (x, y) = \frac{f r e q (x, y)}{Ν} (1)$ $\tilde{Ρ} (x, y) = \frac{f r e q (x, y)}{Ν} (1)$

其中freq (x, y) 是 (x, y) 在样本中出现的次数。

《3 特征与约束》

3 特征与约束

考虑Y的知识环境X, 分析随机过程P, 若考虑所有与Y同现的已有相关知识信息X, 模型的建立相当复杂、烦琐, 从知识创新规律角度分析, Y的生成只与X中部分信息有关, 因此, 从X中找出对Y的取值有价值的知识才是模型所要求的。这些有价值的知识正是随机最大熵模型要寻找的特征。为此, 先定义特征、特征函数、约束。

∀x∈X且x=d, d∈D, D代表x的部分信息, 若d对y∈Y的出现有表征作用, 则称 (d, y) 为模型的一个特征。同时, 事件“d出现时y∈Y出现”在模型中以“0—1”函数的形式表示, 即

$f (x, y) = {\begin{cases} 1 d 出现且 y 出现 \\ 0 否则 \end{cases}$ $f (x, y) = {\begin{cases} 1 d 出现且 y 出现 \\ 0 否则 \end{cases}$

称此函数为特征函数。

为了把有用的特征纳入模型, 可通过增加约束使模型满足相应特征的期望值来实现。进一步的问题是求出在限制条件下具有最一致分布的模型, 此时, 若f对模型有价值, 则期望概率值P (f) 等于经验概率值 $\tilde{Ρ}$ $\tilde{Ρ}$ (f) , 其中

$\begin{array}{l} \tilde{Ρ} (f) = \sum_{x, y} \tilde{Ρ} (x, y) \cdot f (x, y) (2) \\ Ρ (f) = \sum_{x, y} Ρ (x) Ρ (y | x) f (x, y) (3) \end{array}$ $\begin{array}{l} \tilde{Ρ} (f) = \sum_{x, y} \tilde{Ρ} (x, y) \cdot f (x, y) (2) \\ Ρ (f) = \sum_{x, y} Ρ (x) Ρ (y | x) f (x, y) (3) \end{array}$

设存在n个特征f_i (i=1, 2, …, n) , 称

$Ρ (f_{i}) = \tilde{Ρ} (f_{i}) i = 1, 2, \dots ‚ n$ $Ρ (f_{i}) = \tilde{Ρ} (f_{i}) i = 1, 2, \dots ‚ n$

即

$\sum_{x, y} \tilde{Ρ} (x, y) \cdot f (x, y) = \sum_{x, y} Ρ (x) Ρ (y | x) f (x, y)$ $\sum_{x, y} \tilde{Ρ} (x, y) \cdot f (x, y) = \sum_{x, y} Ρ (x) Ρ (y | x) f (x, y)$

为模型的约束, 约束集合为

$C = {p \in Ρ | Ρ (f_{i}) = \tilde{Ρ} (f_{i}), i = 1, 2, \dots, n} 。$ $C = {p \in Ρ | Ρ (f_{i}) = \tilde{Ρ} (f_{i}), i = 1, 2, \dots, n} 。$

《4 随机过程最大熵模型[12]》

4 随机过程最大熵模型[12]

由约束集合定义可知, 满足约束条件的模型很多, 目标是产生在约束集下具有最均匀分布的模型, 即要求出最优的P (y|x) 值需要得到一个最为一致分布的模型, 测量这种一致性的方法之一是条件熵, 即

$Η (p) = - \sum_{x, y} \tilde{Ρ} (x) Ρ (y | x) \lg Ρ (y | x) (4)$ $Η (p) = - \sum_{x, y} \tilde{Ρ} (x) Ρ (y | x) \lg Ρ (y | x) (4)$

或

$Η (p) = - \int \tilde{Ρ} (x) Ρ (y | x) \lg Ρ (y | x) d x (5)$ $Η (p) = - \int \tilde{Ρ} (x) Ρ (y | x) \lg Ρ (y | x) d x (5)$

其中:0≤H (p) ≤lg|y|。

由以上分析可知, 概率预先未知待求, 约束条件是使条件熵H (p) 等于最大值的概率。这正是最大熵原理所解决的问题。最大熵原理最初由E.T.Jayness提出^[13], 1989年A. B. Tepleman 和李兴斯将最大熵法应用于不可微问题的优化^[14], Della Pietra等于1992年首次将它应用于自然语言处理的模型建立中^[15,16,17], Jayness的叙述为“当根据部分信息进行推理时, 我们必须使用具有最大熵值且满足已知条件的概率分布。这是我们能够作出的唯一无偏选择, 若采用任何其他分配就是对原来没有的信息做了任意假设。”

根据最大熵原理, 应该使得P (x) 和f (x) 在已知的特征上表现出相同的统计特性, 同时又要保证不作任何过多的假设, 即要求p (x) 的熵尽可能大。

因此, 在允许的概率分布C中选择模型, 同时又保证不作任何人为的假设, 则具有最大熵的模型p_x∈C为所求, 即

$p^{*} = p_{x} = \arg \max_{p \in C} Η (p) (6)$ $p^{*} = p_{x} = \arg \max_{p \in C} Η (p) (6)$

作为被选定的值p_x是唯一的, 在简单的情况下, p_x可以通过分析得出, 但大多数情况是复杂的, 可通过寻找式 (6) 的等价函数的最优化来实现^[14]。

对每个特征f_i引入lagrange乘子λ_i, 定义lagrange函数

$Λ (p, λ) = Η (p) + \sum_{i} λ_{i} (p (f_{i}) - \tilde{p} (f_{i})) (7)$ $Λ (p, λ) = Η (p) + \sum_{i} λ_{i} (p (f_{i}) - \tilde{p} (f_{i})) (7)$

保持λ固定

$\begin{array}{l} \frac{\partial Λ (p, λ)}{\partial p} = - \tilde{p} (x) (1 + \lg Ρ (y | x)) - \\ \sum_{i} λ_{i} \tilde{p} (x) f_{i} (x, y) \end{array}$ $\begin{array}{l} \frac{\partial Λ (p, λ)}{\partial p} = - \tilde{p} (x) (1 + \lg Ρ (y | x)) - \\ \sum_{i} λ_{i} \tilde{p} (x) f_{i} (x, y) \end{array}$

满足 $\frac{\partial Λ}{\partial p} = 0$ $\frac{\partial Λ}{\partial p} = 0$ 的p^*为最优, 并且使H (p) 得到限制条件下最大值, 此时

$p^{*} (y | x) = \frac{1}{Ζ_{λ} (x)} \exp (\sum_{i} λ_{i} f_{i} (x, y))$ $p^{*} (y | x) = \frac{1}{Ζ_{λ} (x)} \exp (\sum_{i} λ_{i} f_{i} (x, y))$

$Ζ_{λ} (x) = \sum_{y} \exp (\sum_{i} λ_{i} f_{i} (x, y))$ $Ζ_{λ} (x) = \sum_{y} \exp (\sum_{i} λ_{i} f_{i} (x, y))$ 是保证对所有x使得 $\sum_{y} p_{λ}^{*} (y | x) = 1$ $\sum_{y} p_{λ}^{*} (y | x) = 1$ 的范化因子。令

$\begin{array}{l} Ψ (Λ) = Λ (p^{*} ‚ λ) ‚ 则 \\ λ^{*} = \arg \max_{λ} Ψ (Λ) \end{array}$ $\begin{array}{l} Ψ (Λ) = Λ (p^{*} ‚ λ) ‚ 则 \\ λ^{*} = \arg \max_{λ} Ψ (Λ) \end{array}$

《5 特征选择》

5 特征选择

以上建立的模型可以保证不含任何额外的假设, 但不能保证所含特征是最有表征性的特征, 因此, 建立模型的重要环节是特征的选择。

进行特征选取时, 是由特征的信息增益值做标准, 一个特征对所处理的任务带来的信息越多, 该特征越适合引入模型中^[18]。有很多方法来测度这种差异, 如Fisher准则、L²距离度量或Kullback-leibler (KL) 距离法, 从准确性、便于计算的角度考虑, 选择了KL法。首先, 形式化一个特征空间, 所有可能的特征构成候补特征集合F, 根据信息增量标准选择F中的元素形成模型的特征集合。具体步骤:

Step1:设候补特征集合F, 模型选用的特征集合S, 对应模型P_S初始化选用集合, S=Φ

Step2:∀f∈F, 求增益值G_f, 根据是 KL距离, 概率分布p, q的KL距离为

$D (p ∥ q) = \sum_{x} p (x) \ln \frac{p (x)}{q (x)} 。$ $D (p ∥ q) = \sum_{x} p (x) \ln \frac{p (x)}{q (x)} 。$

因此, 加入第n个特征前后, 模型分布与样本分布间的KL距离分别为:

$\begin{array}{l} D (\tilde{p} ∥ p^{(n - 1)}) = \sum_{x} \tilde{p} (x) \ln \frac{\tilde{p} (x)}{p^{(n - 1)} (x)} ‚ \\ D (\tilde{p} ∥ p^{(n)}) = \sum_{x} \tilde{p} (x) \ln \frac{\tilde{p} (x)}{p^{(n)} (x)} ‚ \end{array}$ $\begin{array}{l} D (\tilde{p} ∥ p^{(n - 1)}) = \sum_{x} \tilde{p} (x) \ln \frac{\tilde{p} (x)}{p^{(n - 1)} (x)} ‚ \\ D (\tilde{p} ∥ p^{(n)}) = \sum_{x} \tilde{p} (x) \ln \frac{\tilde{p} (x)}{p^{(n)} (x)} ‚ \end{array}$

则引入第n个特征f_n后的增益值为

$G (p, f_{n}) = D (\tilde{p} ∥ p^{(n - 1)}) - D (\tilde{p} ∥ p^{(n)}) ‚$ $G (p, f_{n}) = D (\tilde{p} ∥ p^{(n - 1)}) - D (\tilde{p} ∥ p^{(n)}) ‚$

所以, 选择的第n个特征为

$f_{\max n} = \arg \max_{f \in F} G (p, f_{n}) 。$ $f_{\max n} = \arg \max_{f \in F} G (p, f_{n}) 。$

Step3:选择具有最大增益值的特征f_{max n}。

Step4:把特征f_{max n}加入集合

$S = (f_{\max 1} ‚ \dots ‚ f_{\max n}) 。$ $S = (f_{\max 1} ‚ \dots ‚ f_{\max n}) 。$

Step5:调整参数值, 计算模型P_S。

Step6:回到Step2。

图1是模型系统流程。椭圆代表数据, 矩形代表过程。

《6 分析与结论》

6 分析与结论

创新随机过程最大熵模型是概率统计、最优化、最大熵原理的完美组合, 是随机性与因果性对立统一的数学模型, 且简洁、易移植, 应用范围广泛。模型的主要特点:

1) 模型的结构决定对不同的任务只是选择不同的特征集合嵌入模型中, 因此, 模型可以被多次利用, 模型的这种通用性和重用性允许使用者处理各种不同性质的任务。

2) 不作未经验证的假设。利用最大熵原理承认已有的事实, 对所选特征没有独立性假设。

3) 采用Kullback-Leibler距离作为特征的约束条件, 可以保证模型结论的准确性。同时, 模型的结构决定其可比照语言处理模型编程, 便于计算机实现。

4) 原始知识得到有效利用。一个特征对所处理的任务带来的信息越多, 该特征越优先引入模型中。从繁杂的原有知识中结构化选取有利于创新知识的集合, 大大降低了知识创新的盲目性。

《图1》

图1 随机过程最大熵模型系统图

Fig.1 Systematic flow chart of model on maximum entropy of knowledge creating stochastic process

展示更多